☆打卡算法☆LeetCode 120. 三角形最小路径和 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个三角形，找出自顶向下的最小路径和。”

题目链接：

来源：力扣（LeetCode）

链接： 120. 三角形最小路径和

2、题目描述

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：
输入： triangle = [[-10]]
输出： -10

二、解题

1、思路分析

本题是一道很经典的动态规划题。

在本题中，给定的三角形的行数为n,第i行包含了i+1个数，如果将每一行左端对齐，就会形成一个等腰直角三角形，比如：

[2] 
[3,4] 
[6,5,7] 
[4,1,8,3]

用f[i][j]表示从三角形顶部走到位置(i,j)的最小路径和。

由于每一步只能移动到下一行相邻的节点上，因此想要走到位置(i,j)，上一步就只能在位置(i-1,j-1)或者位置(i-1,j)上。

因此，状态转移方程为：

f[i][j] = min(f[i-1][j-1],f[i-1][j])+c[i][j]

但是上述状态转移方程，在当j = 0时，f[i-1][j-1]是没有意义的；在当 j = i时，f[i-1][j]是没有意义的，所以修改后的状态转移方程为：

f[i][i] = f[i-1][j-1]+c[i][j]

也就是当我们移动到第i行的最右侧时，只能从第i-1行的最右侧移动过来。

最终的答案就是：

f[n-1][0] 到 f[n-1][n-1] 中的最小值就是要求得值，其中n是三角形的行数。

2、代码实现

代码参考：

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] f = new int[n][n];
        f[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            f[i][0] = f[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; ++j) {
                f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);
            }
            f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int minTotal = f[n - 1][0];
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, f[n - 1][i]);
        }
        return minTotal;
    }
}

3、时间复杂度

时间复杂度 ： O(n²)

其中n是三角形的行数。

空间复杂度： O(n²)

我们需要一个 n * n 的二维数组来存放变量。

三、总结

这道题用了动态规划来解题，推导了状态转移方程。

要注意的一点是，状态转移方程有个边界条件，对于这道题来说，边界条件就是：

f[0][0]=c[0][0]

也就是在三角形的顶部时，最小路径和就等于对应位置的元素值。

然后从1开始递增地枚举i，在[0,i]的范围内递增地枚举j，就完成了所有状态的计算。