三角形最佳路径问题的原理解析

JCSY

三角形最佳路径：
在三角形中，从三角形的顶部到底部的不同路径中，经过路径上的数字之和（路径和）最大的一条路径就是最佳路径（并非唯一）。
注意：
路径上的每一步只能走当前数字下方相邻最近的两个数字之一（正下方或右下方）。
以下图为例：

分析：
采用动态规划思想，首先分解子问题，默认从顶部到底部数字的最佳路径，每一段子路径对应的每一个数字都是最优的。将三角形数字数据存入一个二维数组中，用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[MAX_NUM + 10][MAX_NUM + 10];            //存储三角形的数组
int N;                                        //三角形的层数
int MaxSum[MAX_NUM + 10][MAX_NUM + 10];      //存储每一个点到底层最优路径的值

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[i][j];                        //递归输入各点的值
        for( j = 1; j <= N; j ++ )
                MaxSum[N][j] = D[N][j];          //将底层各点值存入最优路径数组
        //根据转移方程递归计算
        for( i = N ; i > 1 ; i -- )
                for( j = 1; j < i ; j ++ ){
                        if( MaxSum[i][j] > MaxSum[i][j+1] ){
                                MaxSum[i-1][j] = MaxSum[i][j] + D[i-1][j];                               
                        }else{
                                MaxSum[i-1][j] = MaxSum[i][j+1] + D[i-1][j];                               
                        }                       
                }
        //输出最优路径的值
        cout<<"最佳路径的值为："<<endl;
        cout<<MaxSum[1][1]<<endl;
        return 0;
}

对于其他类似题目可根据具体原理进行迁移学习.
动态规划算法的一般步骤：

描述最优解的结构。
对最优解的值进行递归定义。
按照自底向上的方法计算最优解的值。
由第3步计算出的结果构造一个最优解。
使用动态规划求解必须满足的条件：

最优化原理。
无后效性：指一个多阶段决策的问题，每一阶段的决策只取决于前一个阶段的决策，而与更靠前的阶段决策无关。
重叠子问题。
---------------------

原文：https://blog.csdn.net/suoyue_py/article/details/96425824