查看“︁120.Triangle”︁的源代码

=Description=
{{LeetCode
|id=triangle
|no=120
|difficulty=Medium
|category=Dynamic Programming
|collection=Top 150
|title=Triangle
|summary=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:

<syntaxhighlight lang="java">
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
</syntaxhighlight>
Explanation: The triangle looks like:
<syntaxhighlight lang="java">
   2
  3 4
 6 5 7
4 1 8 3
</syntaxhighlight>
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).


Example 2:

<syntaxhighlight lang="java">
Input: triangle = [[-10]]
Output: -10
</syntaxhighlight>

=Solution=
==2D DP==
It works, but not good, especially memory.
{{Submission|runtime=3ms|memory=44.4MB|rp=65.79|mp=13.95}}

<syntaxhighlight lang="java">
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int maxRowSize = triangle.get(triangle.size() -1).size();
        // create an array nxn to store the minimal distance that starts from triangle[i][j]
        int[][] dp = new int[maxRowSize][maxRowSize];

        for(int i = triangle.size() -1; i >=0; i--) {
            List<Integer> row = triangle.get(i);
            for(int j = 0; j < row.size(); j++) {
                if(i < dp.length -1) {
                    // calculate minimal distance and update
                    dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + row.get(j);
                } else {
                    // for the bottom line, there's no subpaths
                    dp[i][j] = row.get(j);
                }
            }
        }
        return dp[0][0];
    }
}
</syntaxhighlight>

== 1D DP==
{{Submission|runtime=2ms|memory=43.61MB|rp=77.3|mp=89.2}}

<syntaxhighlight lang="java">
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 可以直接用 triangle.size();
        int maxRowSize = triangle.get(triangle.size() -1).size();
        // 只需要记录上一次的最短路径
        int[] dp = new int[maxRowSize];

        for(int i = triangle.size() -1; i >=0; i--) {
            List<Integer> row = triangle.get(i);
            for(int j = 0; j < row.size(); j++) {
                if(i < dp.length -1) {
                    // 从左到右更新，正好计算右边的元素时，当前的值已经不需要用到了。所以可以直接更新
                    dp[j] = Math.min(dp[j], dp[j+1]) + row.get(j);
                } else {
                    dp[j] = row.get(j);
                }
            }
        }
        return dp[0];
    }
}
</syntaxhighlight>

[[Category:Algorithm]]
[[Category:Dynamic Programming]]
[[Category:LeetCode]]