POJ-1163-The Triangle-动态规划

简单说下题意：已知多个数字组成一个三角形，从顶点开始，对角地下移，一直到底层，形成一条路径，对该路径上所有元素求和，求这个和Sum最大是多少。

/*动态规划求解。算法复杂度为O(n)。
 */
#include <iostream>

using namespace std;

const int MAX = 5055;
int arr[MAX]; //用一维数组存储三角形的元素值
int dp[MAX]; //存储以该点为顶点的三角形的Sum最大值

int max(int a, int b) {
    return a > b ? a : b;
}

int main()
{
    int n;
    cin >> n;
    /*初始化*/
    int total = n * (n + 1) / 2;
    for(int i = 0; i < total; i++) {
        cin >> arr[i];
    }
    /*对于底层的元素，以其为顶点的三角形的Sum的最大值即为自身*/
    for(int i = total - 1; i > total - 1 - n; i--)
        dp[i] = arr[i];

    int nElem = n - 1; //倒数第二层具有的元素数目
    /*从倒数第二层的元素开始，往前计算dp*/
    for(int i = total - 1 - n; i >= 0; i -= nElem, nElem--) {
        for(int j = i; j > i - nElem; j--) {
            /*状态方程，取在该点对角下面的两个点中数值较大的点与自身相加*/
            dp[j] = arr[j] + max(dp[j + nElem], dp[j + nElem + 1]);
        }
    }

    /*dp[0]即存储了以顶点的Sum的最大值*/
    cout << dp[0] << endl;

    return 0;
}