給定一個(gè)由n行數(shù)字組成的數(shù)字三角形，設(shè)計(jì)一個(gè)算法枚碗，計(jì)算出從三角形的頂至底的一條路徑逾一，使該路徑經(jīng)過的數(shù)字總和最大。
輸入數(shù)據(jù)a[m][n]：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
最優(yōu)解數(shù)組b[m][n]：
分析：
分析：
這是一道典型的動(dòng)態(tài)規(guī)劃問題肮雨，求頂?shù)降椎囊粭l路徑數(shù)字總和最大遵堵，按照動(dòng)態(tài)規(guī)劃思想，從底往上怨规，子問題的和大陌宿，那么父問題的和就大，所以在給數(shù)組打底子的時(shí)候波丰，就要找大的
1壳坪、二位數(shù)組代表什么：b[i][j]代表從這個(gè)點(diǎn)一直走到最后的最大值
2、數(shù)組打底：b數(shù)組把n-1行填充起來
3掰烟、遞推式：根據(jù)題目可知爽蝴，要從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 //行數(shù)
int main(){
int **a=new int*[n]; //接收輸入的數(shù)據(jù)
int **b=new int*[n]; //存放最優(yōu)值蝎亚，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++) //數(shù)組打底工作
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;
}
運(yùn)行截圖
