给定一个由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;
}
运行截图
