3-4 数字三角形问题（算法设计与分析）_数字三角形算法分析

动态规划判断

① 题目需要求“最值”，可以考虑动态规划

② 有比较明显的状态转移。如本题中，一条路径的值和节点密切相关，当前路径的值由节点的值累加转移而来

③ 考虑最优子结构（同时满足重叠子问题是使用DP的必要性）

题目分析

状态是什么

DP要处理状态的转移，因此首先要明确状态是什么。一般地，题目中发生变化的量就是状态。

本题中，发生变化的量是路径和，所以状态就是路径和，状态的转移就是路径和的值的转移

如何改变 / 转移状态？

状态的转移 / 改变依靠的是每一次的决策 / 选择，因此考虑如何改变状态，就是在考虑我们每一次要做什么决策。

显然这道题的决策：选择上一层的一个节点（在左上或右上），然后把自己纳入路径中

这样定义有两种初始情况：

① 三角形的左侧边，这条边上的数字只有右上可取

② 三角形的右侧边，只有左上可取

或者是选择下一层的一个节点（在左下或右下），视角不同

另外，输入的数据使用二维数组进行存储，存储变成了类似于直角三角形的格式，如题目给出的输入

DP数组的定义 & 状态转移方程

一开始的思路

我把DP数组定义为二维数组，DP[i][j]表示以 第 i 层的第 j 个节点(i,j) 作为结尾的路径和最大值

这样一来，题目要求的其实就是最后一层的选择某个节点的最大值

所以我还需要遍历最后一层，选出其中的最大值作为返回

这种思路的状态转移方程为：

优化的思路

想到顶点处只有一个值，那么能否把最后的最大值放在顶点处呢？

这样一来，就类似于比赛机制，两两比较决出胜者，最后登顶的就是最大值。这里有贪心的思想，每一次都取最大的，最终也是最大的。

即把刚才自顶向下的思路，转换为自底向上迭代。

对于(i,j)位置的节点，其进入路径的最大值，就是在下一层的左下路径和、右下路径和的最大值中取得更大的一个，加入进去

状态转移其实和上面的差不多，但是这种思路可以直接利用累加的方式，把最大值积累起来

代码

一开始的思路

注：这里的num数组是对称矩阵，可以用一维数组压缩（感兴趣的话可以自己实现）

#include <iostream>
#include <vector>
#include <algorithm>
 
using std::cin;
using std::cout;
using std::vector;
using std::max;
 
int main()
{
    int n;
    cin >> n;
    // 创建二维数组
    vector<vector<int>> dp(n, vector<int>(n, 0));
    vector<vector<int>> num(n, vector<int>(n, 0));
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            cin >> num[i][j];
        }
    }
	// 初始化
    dp[0][0] = num[0][0];
	
    // 状态转移
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (j ==0) {
                dp[i][j] = dp[i - 1][j] + num[i][0];
            } else if (i == j) {
                dp[i][j] = dp[i - 1][i - 1] + num[i][i];
            } else {
                dp[i][j] = max(dp[i - 1][j] + num[i][j], 
                               dp[i - 1][j - 1] + num[i][j]);
            }
        }
    }
	// 找到最大的路径和
    int maxSum = 0;
    for (int i = 0; i < n; ++i) {
        maxSum = max(maxSum, dp[n - 1][i]);
    }
    cout << maxSum;
    
    return 0;
}

叠加版

#include <iostream>
#include <vector>
#include <algorithm>
 
using std::cin;
using std::cout;
using std::vector;
using std::max;
 
int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> num(n, vector<int>(n, 0));
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            cin >> num[i][j];
        }
    }
 
    // 从倒数第二行开始向上计算最大值
    for (int i = n - 2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            // 当前位置的最大值为当前位置的值加上下一行相邻两个位置的最大值中的较大值
            num[i][j] += max(num[i + 1][j], num[i + 1][j + 1]);
        }
    }
 
    // 最大值即为顶部的数字
    cout << num[0][0];
 
    return 0;
}