Problem Description

在讲述DP算法的时候，一个经典的样例就是数塔问题，它是这样描写叙述的：

有例如以下所看到的的数塔。要求从顶层走究竟层，若每一步仅仅能走到相邻的结点。则经过的结点的数字之和最大是多少？

已经告诉你了，这是个DP的题目，你能AC吗?

 

Input

输入数据首先包含一个整数C,表示測试实例的个数。每一个測试实例的第一行是一个整数N(1 <= N <= 100)。表示数塔的高度，接下来用N行数字表示数塔。当中第i行有个i个整数，且全部的整数均在区间[0,99]内。

 

Output

对于每一个測试实例，输出可能得到的最大和。每一个实例的输出占一行。

 

Sample Input

1
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

 

Sample Output

30

 

Source

2006/1/15 ACM程序设计期末考试

总的来说是dp的入门级题目吧，由于要表示这个状态方程比較简单。从下往上：dp[i][j]+=dp[i+1][j+1],dp[i+1][j]

从上往上呢：dp[i][j]+=max(dp[i-1][j-1],dp[i-1][j];可是从上往下你还要推断两边界的值，当它处于左边界的时候

有dp[i][0]+=dp[i-1][0];右边界则是dp[i][i]+=dp[i-1][j-1];

以下是代码：

/*
从上到下
*/
#include<stdio.h>
#include<iostream>
#define max(a,b) a>b?a:b
using namespace std;
int dp[360][360];
int main()
{
  int t,i,j,n;
  int maxn;
  cin>>t;
  while(t--)
  {
    cin>>n;
    for(i=0;i<n;i++)
        for(j=0;j<=i;j++)
            cin>>dp[i][j];
        for(i=1;i<n;i++)
        {
          dp[i][0]+=dp[i-1][0];
          dp[i][i]+=dp[i-1][i-1];
        }
        for(i=2;i<n;i++)
        {
          for(j=1;j<i;j++)
              dp[i][j]+=max(dp[i-1][j-1],dp[i-1][j]);
        }
        for(maxn=-1,j=0;j<n;j++)
            maxn=max(maxn,dp[n-1][j]);
        cout<<maxn<<endl;
  }
  return 0;
}
/*
从下到上
*/ #include<iostream>
#include<cstdio>
int dp[1001][1001];
#define max(a,b) a>b?
a:b
using namespace std;
int main(int i,int j)
{
    int t;
    int n;
    cin>>t;
    while(t--)
    {
      cin>>n;
      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;
}
相比而言这个会更简单，由于这样它就就归到一个定点，不用推断它是否为最大值了，另一种记忆化搜索，是在动态规划基础上进行优化的