动态规划——数字三角形

问题描述：

给定一个$n$行的三角形矩阵A，第$i$行有$i$列，从左上角出发，每次可以向下或向右下走一步，最终到达底部，把所有经过的位置的数字加起来，最大是多少。

设$F[i][j]$表示从左上角走到第$i$行，第$j$列的最大和，状态转移方程： $$ F[i][j] = A[i][j] + \max \left{\begin{array}{ll} {Ff[i-1][j]} \ {F[i-1][j-1]} & {n > j \geq 1} \ \end{array}\right. \ init: F[0][0] = A[0][0] \ target: \max_{0 \leq i < n} {F[n-1][i]} $$

#include <bits/stdc++.h>

using namespace std;

vector<vector<int> > num(1005, vector<int>(1005));
int n; 
vector<vector<int> > d(1005, vector<int>(1005));

int numTriangle()
{
    d[0][0] = num[0][0];
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j < 1) d[i][j] = d[i - 1][j];
            else if (j == i) d[i][j] = d[i - 1][j - 1];
            else d[i][j] = max(d[i - 1][j], d[i - 1][j - 1]);
            d[i][j] += num[i][j];
        }
    }

    return *max_element(d[n - 1].begin(), d[n - 1].begin() + n);
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            cin >> num[i][j];
        }
    }

    cout << numTriangle() << endl;

    return 0;
}

注意数组d需要全部初始化为INT_MIN， 因为在计算d[i-1][j]的时候，比如说每一行的最后一个元素，其对应的上一行的元素是不存在的，比如：

-1 0
-2 -1

这种情况，根据递推表达式，如果初始化是0，那么显然第二行的-1加上0更大，最终得到的结果反而是-1.

所以可以进行改进，对于边界情况进行特判。这样程序的可读性就提高了。

典型题目：

• POJ 3176 Cow Bowling（数字三角形模板题）
• 一本通-1258：【例9.2】数字金字塔
• 一本通-1288：三角形最佳路径问题