水题

水题

openJ 2760 数字三jo形

题意:三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
设dp[i][j]为第i行j列所能得到的最大和,利用上下行关系列出状态转移方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+num[i][j],自下而上得到最后一行的所有列的状态再比较取最大值即为最后结果。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn =105;
int n,dp[maxn][maxn];
int num[maxn][maxn];
int main()
{
    while(cin>>n)
    {
        int ans=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
                cin>>num[i][j];
        memset(dp,0,sizeof(dp));
        dp[1][1]=num[1][1];
        for(int i=2;i<=n;i++)
            for(int j=1;j<=i;j++)
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+num[i][j];
        for(int i=1;i<=n;i++)
            ans=max(ans,dp[n][i]);
        cout<<ans<<endl;
    }
    return 0;
}