120 Triangle

update 2018-10-07 22:12:28

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.

Basic Idea:

• 思路 1：divide & conquer

  从上往下递归，每次计算下方两个元素为起点到最后一层的最小路径和，输出最小的。注意其中有很多重复操作，可以使用map来去重。

  Java Code:

  class Solution {
      Map<String, Integer> memory = new HashMap<>();
      public int minimumTotal(List<List<Integer>> triangle) {
          if (triangle.size() == 0) return 0;
          int left = helper(triangle, 1, 0);
          int right = helper(triangle, 1, 1);
          return Math.min(left, right) + triangle.get(0).get(0);
      }
  
      private int helper(List<List<Integer>> triangle, int row, int col) {
          if (triangle.size() == row) return 0;
          Integer ret = memory.get(row + "," + col);
          if (ret != null) return ret;
          int left = helper(triangle, row + 1, col);
          int right = helper(triangle, row + 1, col + 1);
          ret = Math.min(left, right) + triangle.get(row).get(col);
          memory.put(row + "," + col, ret);
          return ret;
      }
  }
  

• 思路 2：DP

  通过观察我们发现每层比下一层都少一个元素，于是我们可以利用一个长度等于最后一行数组的dp数组进行推导，每次推导出上面一层每个元素对应的最小路径和，最终dp[0]就是解。

    例如之前题中所给的例子，每次推导出上面一层每个元素对应的最小的路径和：
  
    首先，dp数组为 [4,1,8,3] （最后一层为 Base Case）
    然后倒数第二层，dp数组为 [7,6,10,x] （4+6 和 1+6 中最小的，1+5 和 8+5 中最小的, 7+8 和 7+3 中最小的）
    倒数第三层：dp数组为 [9,10,x,x] （3+7 和 3+6 中最小的, 4+6 和 4+10 中最小的）
    最上面一层 dp数组为 [11,x,x,x] （9+2 和 10+2 中最小的）
    最终结果就是 dp[0]==11
  

  Java Code:

  class Solution {
      public int minimumTotal(List<List<Integer>> triangle) {
          if (triangle.size() == 0) return 0;
          else if (triangle.size() == 1) return triangle.get(0).get(0);
  
          int[] dp = new int[triangle.size()];
  
          // initialize the dp array with values of the bottom layer
          for (int i = 0; i < triangle.size(); ++i) dp[i] = triangle.get(triangle.size() - 1).get(i);
  
          for (int i = triangle.size() - 2; i >= 0; --i) {
              for (int j = 0; j < triangle.get(i).size(); ++j) {
                  dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
              }
          }
          return dp[0];
      }
  }