poj 3176 Cow Bowling (DP)

水的數字三角形，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<iostream>  
#include<cstring>  
#include<cstdlib>  
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<<ans<<endl;  
    }  
    return 0;  
}