DP数字三角形

数字三角形

• 问题描述

  给定一个具有N层的数字三角形，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最小路径得分。

• DP思路

• 递推关系如下

 	trace = triangle[n];

    for(int i = n-1; i >= 1; i--)
        for(int j = 1;j <= i; j++)
            trace[j] = minnum(trace[j], trace[j+1]) + triangle[i][j];

• 完整代码

#include<iostream>
using namespace std;

int minnum(int x, int y);

int main() {
    int n;
    cin>>n;

    int triangle[10][10];
    int *trace;

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


    trace = triangle[n];

    for(int i = n-1; i >= 1; i--)
        for(int j = 1;j <= i; j++)
            trace[j] = minnum(trace[j], trace[j+1]) + triangle[i][j];

    cout<<trace[1]<<endl;

    return 0;
}

int minnum(int x, int y) { 

    return (x>y ? y : x);
}