英文原文
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
Example 1:
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11 Explanation: The triangle looks like: 2 3 4 6 5 7 4 1 8 3 The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
Example 2:
Input: triangle = [[-10]] Output: -10
Constraints:
1 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104
Follow up: Could you do this using only
O(n) extra space, where n is the total number of rows in the triangle?中文题目
给定一个三角形 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 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104
进阶：
- 你可以只使用
O(n)的额外空间（n为三角形的总行数）来解决这个问题吗？
通过代码
高赞题解
🙋 今日打卡～
一、题目分析
题意：
给定三角形，每次只能移动到下一行中的相邻结点，求从顶点到底边的最小路径和。
[][ [2], [3,4], [6,5,7], [4,1,8,3] ] 相邻结点：与(i, j) 点相邻的结点为 (i + 1, j) 和 (i + 1, j + 1)。
分析：
若定义 $f(i, j)$ 为 $(i, j)$ 点到底边的最小路径和，则易知递归求解式为:
$f(i, j) = min(f(i + 1, j), f(i + 1, j + 1)) + triangle[i][j]$
由此，我们将任一点到底边的最小路径和，转化成了与该点相邻两点到底边的最小路径和中的较小值，再加上该点本身的值。这样本题的 递归解法（解法一） 就完成了。
二、具体实现
解法一：递归
[]class Solution { public int minimumTotal(List<List<Integer>> triangle) { return dfs(triangle, 0, 0); } private int dfs(List<List<Integer>> triangle, int i, int j) { if (i == triangle.size()) { return 0; } return Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j); } }
暴力搜索会有大量的重复计算，导致 超时，因此在 解法二 中结合记忆化数组进行优化。
解法二：递归 + 记忆化
在解法一的基础上，定义了二维数组进行记忆化。
[]class Solution { Integer[][] memo; public int minimumTotal(List<List<Integer>> triangle) { memo = new Integer[triangle.size()][triangle.size()]; return dfs(triangle, 0, 0); } private int dfs(List<List<Integer>> triangle, int i, int j) { if (i == triangle.size()) { return 0; } if (memo[i][j] != null) { return memo[i][j]; } return memo[i][j] = Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j); } }
时间复杂度：$O(N^2)$，$N$ 为三角形的行数。
空间复杂度：$O(N^2)$，$N$ 为三角形的行数。
解法三：动态规划
定义二维 dp 数组，将解法二中「自顶向下的递归」改为「自底向上的递推」。
1、状态定义：
$dp[i][j]$ 表示从点 $(i, j)$ 到底边的最小路径和。
2、状态转移：
$dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]$
3、代码实现：
[]class Solution { public int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); // dp[i][j] 表示从点 (i, j) 到底边的最小路径和。 int[][] dp = new int[n + 1][n + 1]; // 从三角形的最后一行开始递推。 for (int i = n - 1; i >= 0; i--) { for (int j = 0; j <= i; j++) { dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j); } } return dp[0][0]; } }
时间复杂度：$O(N^2)$，$N$ 为三角形的行数。
空间复杂度：$O(N^2)$，$N$ 为三角形的行数。
4、空间优化
在上述代码中，我们定义了一个 $N$ 行 $N$ 列 的 $dp$ 数组（$N$ 是三角形的行数）。
但是在实际递推中我们发现，计算 $dp[i][j]$ 时，只用到了下一行的 $dp[i + 1][j]$ 和 $dp[i + 1][j + 1]$。
因此 $dp$ 数组不需要定义 $N$ 行，只要定义 $1$ 行就阔以啦。
所以我们稍微修改一下上述代码，将 $i$ 所在的维度去掉（如下），就可以将 $O(N^2)$ 的空间复杂度优化成 $O(N)$ 啦～
[]class Solution { public int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); int[] dp = new int[n + 1]; for (int i = n - 1; i >= 0; i--) { for (int j = 0; j <= i; j++) { dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j); } } return dp[0]; } }
时间复杂度：$O(N^2)$，$N$ 为三角形的行数。
空间复杂度：$O(N)$，$N$ 为三角形的行数。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 192201 | 281535 | 68.3% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
