动态规划数字三角形

---

---

给定一个由n行数字组成的数字三角形，设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
输入数据a[m][n]：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
最优解数组b[m][n]：

分析：

分析：
　　这是一道典型的动态规划问题，求顶到底的一条路径数字总和最大，按照动态规划思想，从底往上，子问题的和大，那么父问题的和就大，所以在给数组打底子的时候，就要找大的
1、二位数组代表什么：b[i][j]代表从这个点一直走到最后的最大值
2、数组打底：b数组把n-1行填充起来
3、递推式：根据题目可知，要从n-2行往0行遍历，也就是从下往上。公式为：b[m][n]=max{ b[m+1][n]+a[m][n] , b[m+1][n+1]+a[m][n] }

#include<stdio.h>
#define n 5           //行数 

int main(){
    int **a=new int*[n];  //接收输入的数据 
    int **b=new int*[n];  //存放最优值，b[i][j]存放着a[i][j]到底端的最大路径的和 
    for(int i=0;i<n;i++){
        a[i]=new int[n];
        b[i]=new int[n];
    } 
    for(int i=0;i<n;i++){          
        for(int j=0;j<=i;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=0;i<n;i++)     //数组打底工作
        b[n-1][i]=a[n-1][i];
    for(int i=n-2;i>=0;i--){
        for(int j=0;j<=i;j++){
    b[i][j]=(b[i+1][j]+a[i][j])>(b[i+1][j+1]+a[i][j])?(b[i+1][j]+a[i][j]):(b[i+1][j+1]+a[i][j]);
        }
    }
    printf("%d\n",b[0][0]);
    return 0;
} 

运行截图