itdef

 經典動態規劃問題

給出一個數值均在0~99之間的三角形

請問從第一行的數字出發，每次可選擇下一行相鄰的兩個數字中的一個，請問達到底層的時候選擇的所有數字和最大是多少

輸入 第一行一個數字N 表示三角形有N行，后面N行每行有1~N個空格隔開的數字

輸出 一行 包含一個答案數字

// 1123555.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 = 370;
int arr[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];
        }
    }

#if 1
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            int val = max(arr[i+1][j], arr[i+1][j + 1]);
            arr[i][j] += val;
        }
    }
    cout << arr[0][0] << endl;
#else
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            int val = arr[i][j];
            if (j < i)
            {
                arr[i][j] = max(arr[i][j], val + arr[i - 1][j]);
            }
            if (j > 0) {
                arr[i][j] = max(arr[i][j], val + arr[i - 1][j - 1]);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, arr[n - 1][i]);
    }

    cout << ans << endl;
#endif



    return 0;
}