动态规划 入门 POJ-1163 The Triangle

题目链接：[ POJ - 1163 ]

题目大意

用二维数组存放数字三角形。

D(r, j) : 第r行第j个数字(r, j从1开始算)
MaxSum(r, j) : 从D(r, j)到底边的各条路径中，最佳路径的数字之和。
问题:求 MaxSum(1, 1)

思路

典型的递归问题。
D(r, j) 出发，下一步只能走 D(r+1,j) 或者 D(r+1, j+1)。故对于N行的三角形:

 if ( r == N)  
    MaxSum(r,j) = D(r,j)  
 else  
    MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j)  

但是！会超时!
如果每算出一个 MaxSum(r,j) 就保存起来，下次用到其值的时候直接取用，则可免去重复计算。
那么可以用 $O(n^2)$ 时间完成计算。因为三角形的数字总 数是 $n(n+1) {\div} 2$

然后我们将递归转化为递推即可，之后进行空间优化：
没必要用二维maxSum数组存储每一个 MaxSum(r,j) ,只要从底层一行行向上递推，
那么只要一维数组maxSum[100]即可,即只要存储一行的MaxSum值就可以。

题解代码

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100 + 10;
int dp[maxn];
int map[maxn][maxn];

int main(void)
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            scanf("%d", &map[i][j]);

    for(int i = 1; i <= n; i++)
        dp[i] = map[n][i];

    for(int i = n - 1; i > 0; i--)
        for(int j = 1; j <= i; j++)
            dp[j] = max(dp[j], dp[j+1]) + map[i][j];
    cout << dp[1] << endl;

    return 0;
}