【LeetCode】动态规划—120. 三角形最小路径和（附完整Python/C++代码）

前言

三角形最小路径和 是动态规划问题的经典应用之一。在给定一个三角形数组时，如何从顶部到底部找到最小的路径和？这类问题不仅考验我们的动态规划思维，也要求我们有效地优化空间和时间复杂度。

通过自底向上的动态规划方法，我们可以逐层计算出最优解，而不必枚举所有路径。本文将详细介绍如何通过动态规划解决这个问题，结合 Python 和 C++ 实现来帮助你理解每一步的细节和优化过程。

题目描述

基本思路

1. 问题定义

给定一个三角形的二维数组 triangle，其中 triangle[i] 表示三角形第 i 层的数字。你需要从三角形的顶层开始移动到底层，移动的规则是每次只能移动到下一层相邻的数字。要求找到从顶层到底层的最小路径和。

2. 理解问题和递推关系

问题的本质是一个典型的动态规划问题，核心是从三角形的顶端到底端的最小路径和。可以通过自底向上的动态规划来解决这个问题:

• 定义一个 dp 数组，其中 $dp[i][j]$ 表示从 $(i,j)$ 位置到底层的最小路径和。

• 递推关系：

$$dp[i][j]=\min (dp[i+1][j],dp[i+1][j+1])+\mathrm{triangle}[i][j]$$

意思是当前位置的最小路径和等于当前位置的值加上下一层相邻两个位置中的较小值。

3. 解决方法

3.1 动态规划方法

1. 自底向上计算最小路径和，首先初始化最后一层的 dp 值为三角形最后一层的值。
2. 从倒数第二层开始，逐层向上计算每个位置的最小路径和，更新 dp 数组。
3. 最终 dp[0][0] 即为从顶层到底层的最小路径和。

3.2 空间优化的动态规划

• 由于每次计算只需要下—层的状态，因此可以优化空间复杂度，只使用一个一维数组 dp 来存储每一层的最小路径和，逐层更新。

4. 进一步优化

• 空间优化：可以将空间复杂度从 $O\left(n^{\wedge }2\right)$ 降低到 $O(n)$ ，只需一个一维数组来存储当前层的状态。
• 自底向上计算：动态规划方法从底部向顶部计算，每一层的结果依赖于下一层的值，因此可以直接在原数组上操作，进一步减少空间开销。

5. 小总结

• 动态规划提供了一种从底向上的方法来有效解决该问题，时间复杂度为 $O\left(n^{\wedge }2\right)$ ，空间复杂度可以优化为 $O(n)$ 。
• 动态规划的关键是找到合适的状态转移方程，在本题中，我们通过递推公式逐步求解每一层的最小路径和，最终得到全局最优解。

以上就是三角形最小路径和问题的基本思路。

代码实现

Python

Python代码实现

class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        if not triangle:
            return 0
        
        n = len(triangle)
        # 初始化dp数组，最后一层即为dp的初始值
        dp = triangle[-1][:]
        
        # 从倒数第二层开始向上计算
        for i in range(n - 2, -1, -1):
            for j in range(len(triangle[i])):
                # 更新dp[j]为当前层的最小路径和
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
        
        # dp[0]存储的是从顶到底的最小路径和
        return dp[0]

Python 代码解释

• 初始化：将 dp 数组初始化为三角形最后一层的值，作为最底层的初始状态。
• 自底向上计算：从倒数第二层开始，逐层向上计算每个位置的最小路径和，通过更新 dp 数组来保存当前层的最优解。
• 返回结果：最终返回 dp[0]，即从顶到底的最小路径和。

C++

C++代码实现

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if (triangle.empty()) return 0;
        
        int n = triangle.size();
        // 初始化dp数组，最后一层即为dp的初始值
        vector<int> dp(triangle[n - 1]);
        
        // 从倒数第二层开始向上计算
        for (int i = n - 2; i >= 0; --i) {
            for (int j = 0; j < triangle[i].size(); ++j) {
                // 更新dp[j]为当前层的最小路径和
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
            }
        }
        
        // dp[0]存储的是从顶到底的最小路径和
        return dp[0];
    }
};

C++ 代码解释

• 初始化：创建 dp 数组，将其初始化为三角形最后一层的值。
• 自底向上递推：从倒数第二层开始，逐层更新 dp 数组中的最小路径和。每个位置的值通过取下一层相邻位置的较小值加上当前值得到。
• 返回结果：最终 dp[0] 即为从顶到底的最小路径和。

总结:

• 动态规划是解决路径优化问题的常用方法之一。通过自底向上的方式，我们可以在不遗漏任何可能性的情况下找到最优解。本题中，空间复杂度可以从 $O(n^2)$ 优化到 $O(n)$，即使用一维数组来保存状态。
• 动态规划的核心是通过递推公式计算每个位置的最小路径和，并在全局最优解的基础上不断更新当前的最优解。理解这些技巧将为解决更多类似的路径问题提供坚实的基础。