120. Triangle.md

120. Triangle

---

leetcode Daily Challenge on July 14th, 2020.

---

Difficulty : Medium

Related Topics : Array、Dynamic Programming

---

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

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

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

• Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

---

Solution

• mine
  • Java

    • DP Bottom-Up Runtime: 3 ms, faster than 52.92%, Memory Usage: 40.4 MB, less than 17.46% of Java online submissions

      // O(N^2)time  1 + 2 + 3 + ... + N
      // O(N)space  
      // N = triangele.length
      public int minimumTotal(List<List<Integer>> triangle) {
          int n;
          if(triangle == null || (n = triangle.size()) == 0){
              return 0;
          }
          int[][] dp = new int[2][n];
          dp[0][0] = triangle.get(0).get(0);
          for(int i = 1; i < n; i++){
              List<Integer> t = triangle.get(i);
              for(int j = 0; j <= i; j++){
                  if(j == 0){
                      dp[i & 1][j] = dp[(i - 1) & 1][j]  + t.get(j);
                      continue;
                  }
                  if(j == i){
                      dp[i & 1][j] = dp[(i - 1) & 1][ j - 1]  + t.get(j);
                      continue;
                  }
                  dp[i & 1][j] = Math.min(dp[(i - 1) & 1][ j - 1], dp[(i - 1) & 1][ j]) + t.get(j);
              }
          }
          int res = Integer.MAX_VALUE;
          for(int i : dp[(n - 1) & 1]){
              res = Math.min(res, i);
          }
          return res;
      }
      

    • DP Top-Down Runtime: 3 ms, faster than 52.92%, Memory Usage: 39.2 MB, less than 92.38% of Java online submissions

      // O(N^2) time  N = triangle.size()
      // O(1) space
      public int minimumTotal(List<List<Integer>> triangle) {
          int n;
          if(triangle == null || (n = triangle.size()) == 0){
              return 0;
          }
          for(int i = n - 1; i > 0; i--){
              List<Integer> t = triangle.get(i);
              List<Integer> up = triangle.get(i - 1);
              for(int j = 0; j < i; j++){
                  up.set(j, up.get(j) + Math.min(t.get(j), t.get(j + 1)));
              }
          }
          return triangle.get(0).get(0);
      }
      

---