POJ-1163 The Triangle[动态规划]

原题在这里

题目给出一个这样的数字三角形，定义这个三角形上的一条路径是从最上面一个数字出发向下逐层移动，每次移动时可以选择想左下移动或是向右下移动。移动过程中将途径点上的数字加起来，要求求出最大的和。

测试例子里给出来的的三角形是这样的

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

所以合法的移动方向实际上是向下或向右下。所以在每个节点我们都有两个可能的选择，我们每次移动都需要在这两个选择中抉择，假设我们走到第i行第j个元素时的最大值为dp[i][j], 则dp[i][j] = max(dp[i-1][j]+arr[i][j], dp[i-1][j-1]+arr[i][j]), 需要初始化的就是dp[0][0], 然后结果就是最后一行元素中的最大值了。
反着从最后一行开始计算也可以, 思想都是一样的, 程序就是下面这个:

#include 
#include 
#include 

using namespace std;

int tri[105][105];
int dp[105][105];
int main(void)
{
    int N;
    scanf("%d", &N);
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j <= i; ++j) {
            scanf("%d", &tri[i][j]);
        }
    }
    for(int i = 0; i < N; ++i) {
        dp[N-1][i] = tri[N-1][i];
    }
    for(int i = N-1; i >= 0; --i) {
        for(int j = 0; j < N; ++j) {
            dp[i][j] = max(dp[i+1][j]+tri[i][j], dp[i+1][j+1]+tri[i][j]);
        }
    }
    printf("%dn", dp[0][0]);
    return 0;
}