Title: Sum of minimum paths of triangles

Description: Given a triangle, find the minimum sum of paths from top to bottom. Each step can only move to the next node in the next row.

Adjacent nodes in this case are two nodes whose subscripts are the same or equal to the subscripts of the nodes at the previous level + 1.

For example, given a triangle:

[[2], [3,4], [6,5,7], [4,1,8,3]Copy the code

The minimum sum of paths from top to bottom is 11 (that is, 2 + 3 + 5 + 1 = 11).

Source: leetcode-cn.com/problems/tr…

Analysis of the topic:

If defined as 为 The minimum path sum of the bottom edge of the point, then it is easy to know the recursive solution formula is:


Thus, we convert the minimum sum of paths at the bottom edge of any point into the minimum sum of paths at the bottom edge of two adjacent points, plus the value of the point itself. So the recursive solution (solution one) is done.

The specific implementation

Solution one: recursion

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); }}Copy the code

Solution two: recursion + memorization

On the basis of solution 1, a two-dimensional array is defined for memorization.

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); }}Copy the code
  • Time complexity:N is the number of rows of a triangle.
  • Space complexity:N is the number of rows of a triangle.

Solution three: dynamic programming

Define a two-dimensional DP array and change “top-down recursion” to “bottom-up recursion” in solution 2.

  1. State definition:Says from the point ofThe minimum sum of paths to the bottom.

  2. State transition:


  1. Code implementation:
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        // dp[I][j] represents the minimum sum of paths from point (I, j) to the bottom edge.
        int[][] dp = new int[n + 1][n + 1];
        // Start from the last line of the triangle.
        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]; }}Copy the code
  • Time complexity:N is the number of rows of a triangle.
  • Space complexity:N is the number of rows of a triangle.
  1. Spatial optimization In the above code, we define one 行 The columnArray (Is the number of rows of a triangle. But in the actual recursion we found that the computationIs used only in the next line 和 soArrays don’t need to be definedOk, just define itLine is broad with. So let’s modify the above code a little bitRemove the dimension (as follows) from which it is locatedThe space complexity is optimized into
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]; }}Copy the code
  • Time complexity:N is the number of rows of a triangle.
  • Space complexity:N is the number of rows of a triangle.