Poj1163

很简单很典型的一道DP题。

先解释下大概意思。给你一个三角形数阵，第i行就有i个数，如最上面的图。你在最上面开始往下走，每次可以往左下或者右下走，最后把你走过的地方的和加起来，求这个和可能达到的最大值。

重要的式子是：dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i-1][j-1]+a[i][j]);

下面附上我的代码：

#include <stdio.h>

#define max(a,b) ((a)>(b))?(a):(b)

int main( )

{

       int n,i,j,a[102][102]={0},dp[102][102]={0},max=0;

       scanf("%d",&n);

       for(i=1;i<=n;i++)

                  for(j=1;j<=i;j++)

                         scanf("%d",&a[i][j]);

           for(i=1;i<=n;i++)

                  for(j=1;j<=i;j++)

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

           for(i=1;i<=n;i++){

                  if(max<dp[n][i]) 

                          max=dp[n][i];

               }

           printf("%d\n",max);

return 0;

}