POJ 3176 Cow Bowling

 

 有一个金字塔，一颗球只能滚到他的下面左边的那一个或右边的那一个，问经过的最大数值总和是多少

经典 DP：dp[i][j] 表示到达第 i 层的第 j 个数字后的最大总和

dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j] 

const int N=350+5;
 
    int n,m,t;
    int i,j,k;
    int a[N][N];
    int dp[N][N];
    
int main()
{
    //IOS;
    while(~sd(n)){
        for(i=1;i<=n;i++){
            for(j=1;j<=i;j++){
                sd(a[i][j]);
                //printf("%d ",a[i][j]);
            }
            //puts("");
        }
        for(i=1;i<=n;i++){
            for(j=1;j<=i;j++){
                dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
            }
        }
        int ans=0;
        for(i=1;i<=n;i++) ans=max(ans,dp[n][i]);
        pd(ans);
    }
    //PAUSE;
    return 0;
}