poj 3176 dp

地址 http://poj.org/problem?id=3176

大致题意：

输入一个n层的三角形，第i层有i个数，求从第1层到第n层的所有路线中，权值之和最大的路线。

规定：第i层的某个数只能连线走到第i+1层中与它位置相邻的两个数中的一个。

数值范围 0~350

Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30

样例路线

Hint

Explanation of the sample:

          7

         *

        3   8

       *

      8   1   0

       *

    2   7   4   4

       *

  4   5   2   6   5

解答

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] = 三角形[0][0];

// poj3176.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>



using namespace std;

/*
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5


Sample Output
30
*/

const int N = 500;

int arr[N][N];
int dp[N][N];
int n;


int main()
{
    cin >> n;

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

    dp[0][0] = arr[0][0];

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

    int ans = -9999999;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[n - 1][i]);
    }

    cout << ans << endl;
}