DP 数字三角形(POJ1163)-蒲公英云

DP 数字三角形(POJ1163)

朱雀 2022-08-18 02:36 137阅读 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
*/