动态规划—Problem F

动态规划—Problem F
题意
数塔问题，有数塔（类似于三角形数字但稍有不同），要求从顶层走到底层，若每一步只能走到相邻的结点，求经过的结点的数字之和最大是多少。
解题思路
可以采用从下往上的思路，即从最后一排的数向上递推，这时候的状态方程为：dp[i][j]+=dp[i+1][j+1],dp[i+1][j]；按照这种方式求最大值就可以了。
感想
算是入门的题目吧，比较简单。
AC代码

#include<iostream>
#include<cmath>
using namespace std;
#define MAX 1010

int dp[MAX][MAX];

int main()
{
  int t;
  int n;
  cin>>t;
  while(t--)
  {
    cin>>n;
    int i,j;
    for(i=0;i<n;i++)
      for(j=0;j<=i;j++)
        cin>>dp[i][j];
      for(i=n-1;i>=0;i--)
        for(j=0;j<=i;j++)
          dp[i][j]+=max(dp[i+1][j+1],dp[i+1][j]);
        cout<<dp[0][0]<<endl;
  }
   return 0;
}