ディジタルさんかくけいもんだい


ディジタルさんかくけいもんだい


Description
次の図はデジタル三角形を示しています.プログラムを作成して、上から下までのどこかのパスを計算して、そのパスが通る数字と最大を計算してください.
Input
複数のテストケースがあり、各テストケースについて、キーボードで行単位で入力し、1行目は入力整数(この整数が0の場合は終了を表し、再処理は不要)で、三角形の行数n、次いでnの行数を表す
Output
最大値を出力
Example Input
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Example Output
30

コードブロック

#include
#include
#define MAX 1000
using namespace std;
int data[MAX][MAX];   // 
int dp[MAX][MAX];     // 
int tower_walk(int n)
{
    //dp 
    for(int i=0; i1][i] = data[n-1][i];

    int temp_max;        // 
    for(int i=n-2; i>=0; i--)
        for(int j=0; j<=i; j++)
        {
            temp_max = max(dp[i+1][j],dp[i+1][j+1]);
            dp[i][j] = temp_max + data[i][j];
        }
}

// 
int print(int n)
{
    cout << " :" << dp[0][0] << endl;
    int node_value;

    // 
    cout << " :" << data[0][0];

    int j=0;
    for(int i=0; iif(node_value == dp[i][j+1])
            j++;
        cout << " -> " << data[i][j]; 
    } 
    cout << endl;
}

int main()
{
    int n;                           // n 
    cin >> n;
    for(int i=0; ifor(int j=0; j<=i; j++)
            cin >> data[i][j];       
    tower_walk(n);
    cout << dp[0][0] << endl;        // dp[0][0] 
    return 0;

}