三角形最佳路径问题的原理解析
三角形最佳路径：在三角形中，从三角形的顶部到底部的不同路径中，经过路径上的数字之和（路径和）最大的一条路径就是最佳路径（并非唯一）。
注意：
路径上的每一步只能走当前数字下方相邻最近的两个数字之一（正下方或右下方）。
以下图为例：
分析：
采用动态规划思想，首先分解子问题，默认从顶部到底部数字的最佳路径，每一段子路径对应的每一个数字都是最优的。将三角形数字数据存入一个二维数组中，用D(i，j)表示第 i 行第 j 列的数字值。从D(i，j)出发，则下一步为D(i+1，j)或D(i+1，j+1)。从而推导出递推公式。
主要思路：
从最后一行开始向上递推，判断正下方和右下方谁的数大，选择之后加到上一行，生成一个新的数。
第一轮：
原第四行数值
2==> 2+5=7
7==> 7+5=12
4==> 4+6=10
4==> 4+6=10
第二轮：
原第三行数值
8==> 8+12=20
1==> 1+12=13
0==> 0+10=10
第三轮：
原第二行数值
3==> 3+20=23
8==> 8+13=21
第四轮：
原第一行数值
7==> 7+23=30
最后得到的最大值为：30，即三角形最佳路径为30.
具体完整的代码如下：
#include <iostream>
#define MAX_NUM 100
using namespace std;
//动态规划求三角形最佳路径值
int D; //存储三角形的数组
int N; //三角形的层数
int MaxSum; //存储每一个点到底层最优路径的值
int main()
{ int i, j;
cout<<"请输入三角形行数："<<endl;
cin>>N; //输入N值
cout<<"请输入三角形各点数值:"<<endl;
for( i = 1; i <= N; i ++ )
for( j = 1; j <= i; j ++ )
cin>>D; //递归输入各点的值
for( j = 1; j <= N; j ++ )
MaxSum = D; //将底层各点值存入最优路径数组
//根据转移方程递归计算
for( i = N ; i > 1 ; i -- )
for( j = 1; j < i ; j ++ ){
if( MaxSum > MaxSum ){
MaxSum = MaxSum + D;
}else{
MaxSum = MaxSum + D;
}
}
//输出最优路径的值
cout<<"最佳路径的值为："<<endl;
cout<<MaxSum<<endl;
return 0;
}
对于其他类似题目可根据具体原理进行迁移学习.
动态规划算法的一般步骤：
描述最优解的结构。
对最优解的值进行递归定义。
按照自底向上的方法计算最优解的值。
由第3步计算出的结果构造一个最优解。
使用动态规划求解必须满足的条件：
最优化原理。
无后效性：指一个多阶段决策的问题，每一阶段的决策只取决于前一个阶段的决策，而与更靠前的阶段决策无关。
重叠子问题。
---------------------
原文：https://blog.csdn.net/suoyue_py/article/details/96425824
页:
[1]