DP 数字三角形(POJ1163)

朱雀 2022-08-18 02:36 5阅读 0赞

3 8

8 1 0

2 7 4 4

4 5 2 6 5

在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。

路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。

三角形的行数大于1小于等于100，数字为0 -99

“人人为我”递推型动归程序

a(i,j) : 第i行第j个数字(i,j从1开始算)

dp(i,j) : 从a(i,j)到底边的各条路径中，最佳路径的数字之和。

问题：求dp(1,1)

D(r, j)出发，下一步只能走D(r+1,j)或者D(r+1, j+1)。故对于N行的三角形：

if ( r == N)

MaxSum(r,j) = D(r,j)

else

MaxSum( r, j) = Max\{ MaxSum(r＋1,j), MaxSum(r+1,j+1) \} + D(r,j)

#include <iostream>
    #include <cstdio>
    #include <cmath>
    using namespace std;
    
    int main()
    {
        int t,n;
        int dp[105][105];
        int a[105][105];
        //scanf("%d",&t);
        while(scanf("%d",&n)!=EOF)
        {
    
            for(int i = 1 ; i <= n ; i++)
            {
                for(int j = 1 ; j <= i ; j++)
                {
                    scanf("%d",&a[i][j]);
                }
            }
            for(int i = n ; i >= 1 ; i--)
            {
                for(int j = 1 ; j <= i ; j++)
                {
                    if(i==n)dp[i][j]=a[i][j];
                    else
                    {
                        dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
                    }
                }
            }
    //        for(int i = 1 ; i <= n ; i++)
    //        {
    //            for(int j = 1 ; j <= i ; j++)
    //            {
    //                printf("%d ",dp[i][j]);
    //            }
    //            printf("\n");
    //        }
            printf("%d\n",dp[1][1]);
        }
        return 0;
    }
    
    /*
    Auther:LIUYAN
    2015.11.30
    数字三角形(POJ1163)
    100
    5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
    */