poj 3176 Cow Bowling (DP) - c++编程基础

水的数字三角形，DP转移方程： dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+num[i][j].(j>1);

dp[i][j]=dp[i-1][j]+num[i][j] (j==1)

在最后一行dp[N][i]中找最大即可。

代码：

 
#include  
#include  
#include  
using namespace std;  
const int MAXN=351;  
int dp[MAXN][MAXN];   
int num[MAXN][MAXN];  
int main()  
{  
    int N;  
    while(cin>>N)  
    {  
        memset(dp,0,sizeof(dp));  
        for(int i=1;i<=N;i++){  
            for(int j=1;j<=i;j++)  
                cin>




>num[i][j];  
        }  
        dp[1][1]=num[1][1];  
        for(int i=2;i<=N;i++){  
            for(int j=1;j<=i;j++){  
                if(j==1) dp[i][j]=dp[i-1][j]+num[i][j];  
                else dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+num[i][j];  
            }  
        }   
        int ans=0;  
        for(int i=1;i<=N;i++) ans=max(ans,dp[N][i]);  
        cout<