[LeetCode] 120. Triangle

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 <= 200
triangle[0].length == 1
triangle[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 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

首先将数组变成一个直角三角形这样易于理解。

[2]

[3,4]

[6,5,7]

[4,1,8,3]

思路是自下而上的动态规划，我参考了这个帖子。题目求的是自上而下的最小路径和，那么也就意味着在每两个相邻的数字之间，要找出一个相对小的数字，才有可能使得整个路径最小，但是如果自上而下这样找的话，其实并不一定能找到整个路径最小的。所以这里创建一个长度为 triangle.size() + 1 的数组记录最后动态规划的结果。从最后一行开始扫描，在 DP 数组的每一个位置上的值是当前位置 i 的数字 + DP数组里面 dp[i] 和 dp[i + 1] 的较小的值。最后返回的是 dp[0]。图示如下

时间O(n^2)

空间O(n)

Java实现

 1 class Solution {
 2     public int minimumTotal(List<List<Integer>> triangle) {
 3         int[] res = new int[triangle.size() + 1];
 4         for (int i = triangle.size() - 1; i >= 0; i--) {
 5             for (int j = 0; j < triangle.get(i).size(); j++) {
 6                 res[j] = Math.min(res[j], res[j + 1]) + triangle.get(i).get(j);
 7             }
 8         }
 9         return res[0];
10     }
11 }

JavaScript实现

 1 /**
 2  * @param {number[][]} triangle
 3  * @return {number}
 4  */
 5 var minimumTotal = function(triangle) {
 6     // corner case
 7     if (triangle === null || triangle.length === 0) {
 8         return 0;
 9     }
10 
11     // normal case
12     let res = new Array(triangle.length + 1).fill(0);
13     for (let i = triangle.length - 1; i >= 0; i--) {
14         for (let j = 0; j < triangle[i].length; j++) {
15             res[j] = Math.min(res[j], res[j + 1]) + triangle[i][j];
16         }
17     }
18     return res[0];
19 };