Skip to content

Latest commit

 

History

History
281 lines (219 loc) · 8.59 KB

120.triangle.md

File metadata and controls

281 lines (219 loc) · 8.59 KB
  1. Triangle

中等

https://leetcode-cn.com/problems/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?

相关标签

  • Array
  • Dynamic Programming

Scale of the problem: n^2 not 2^n

Because the right child of a node is also the left child of next node at same level. This is different from Binary Tree, whose scale is 2^n.

n^2 Triangle

    2
   / \
  3   4
 / \ / \
6   5   7  # this 5 is 3's right child also 4's left child

2^n Binary Tree

     2
   /   \
  3     4
 / \   / \
6   5 7   8

Solution 1 DFS-Traverse 遍历 -- O(2^n) 超出时间限制. No pruning.

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        self.minTotal = sys.maxsize
        self.__traverse(triangle, 0, 0, 0)
        return self.minTotal

    def __traverse(self, triangle, leftChild, rightChild, pathsum):
        if leftChild == len(triangle):
            self.minTotal = min(self.minTotal, pathsum)
            return

        self.__traverse(triangle, leftChild + 1, rightChild, pathsum + triangle[leftChild][rightChild])
        self.__traverse(triangle, leftChild + 1, rightChild + 1, pathsum + triangle[leftChild][rightChild])
     2
   /   \
  3     4
 / \   / \
6   5 5   7 # 5 is calculated twice
  • If len(triangle == 1, 1 path
  • if == 2, 2 paths
  • if == 3, 4 paths
  • if == 4, 8 paths
  • so .. O(2^n)

Solution 2 DFS-Divide & Conquer -- O(2^n). 超出时间限制. No Pruning.

仍旧为O(2^n), 因为没有剪枝，还是会 走一遍所有点。

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        return self.__divide_conquer(triangle, 0, 0)

    def __divide_conquer(self, triangle, leftchild, rightchild):
        if leftchild == len(triangle):
            return 0

        leftpathsum = self.__divide_conquer(triangle, leftchild+1, rightchild)
        rightpathsum = self.__divide_conquer(triangle, leftchild+1, rightchild+1)
        return min(leftpathsum, rightpathsum) + triangle[leftchild][rightchild]

Solution 3 Divid-Conquer with memo = 记忆化搜索Memoization Search O(n^2)

注意不是memorization

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        return self.__divide_conquer_memo(triangle, 0, 0, {})
        
    # 函数返回从 x, y 出发，走到最底层的最短路径值
    # memo 中 key 为二元组 (x, y)
    # memo 中 value 为从 x, y 走到最底层的最短路径值
    def __divide_conquer_memo(self, triangle, x, y, memo):
        if x == len(triangle):
            return 0
            
        # 如果找过了，就不要再找了，直接把之前找到的值返回
        if (x, y) in memo:
            return memo[(x, y)]

        left = self.__divide_conquer_memo(triangle, x + 1, y, memo)
        right = self.__divide_conquer_memo(triangle, x + 1, y + 1, memo)
        
        # 在 return 之前先把这次找到的最短路径值记录下来
        # 避免之后重复搜索
        memo[(x, y)] = min(left, right) + triangle[x][y]
        return memo[(x, y)]
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        HashMap<String, Integer> memo = new HashMap<String, Integer>();
        return this.divideConquerMemo(triangle, 0, 0, memo);
    }

    private int divideConquerMemo(List<List<Integer>> triangle, int leftchild, int rightchild, HashMap<String, Integer> memo){
        if (leftchild == triangle.size()){
            return 0;
        }

        String currKey = String.valueOf(leftchild*100) + String.valueOf(rightchild*100); // Need to ensure this key is unique. Avoid "1"+"12" == "11"+"2".
        if (memo.get(currKey) != null ) {
            return memo.get(currKey);
        }

        int leftpathsum = this.divideConquerMemo(triangle, leftchild+1, rightchild, memo);
        int rightpathsum = this.divideConquerMemo(triangle, leftchild+1, rightchild+1, memo);
        memo.put(currKey, Math.min(leftpathsum, rightpathsum) + triangle.get(leftchild).get(rightchild));
        return memo.get(currKey);
    }
}
      2
     / \
    3   4
   / \ / \
  6   5   7  
 / \ / \ / \
4   1   8   3

Take 8 as example, it will be calculated twice. First is when go to 5, it calls 8 and memo it. Second is when go to 7, it calls 8 and retrive from memo.

So each (x, y) will be called twice. There are 1 + 2 + 3 + 4 + ... = (1+n)n/2 nodes. Each node called twice. So totally call (1+n)n/2 * 2 times = O(n^2).

Solution 4 DP Botttom up forloop. Time O(n^2) Space O(n^2)

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # bottom up
        n = len(triangle)
        
        # state: dp[i][j] 代表从 i,j  走到最底层的最短路径值
        dp = [[0] * (i + 1) for i in range(n)] # 第i行长度为i+1
        
        # initialize: 初始化终点（最后一层）
        for i in range(n):
            dp[n - 1][i] = triangle[n - 1][i] # 最后一行直接复制
            
        # function: 从下往上倒过来推导，计算每个坐标到哪儿去
        # dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
        for i in range(n - 2, -1, -1):#每行
            for j in range(i + 1):#行内
                dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
                
        # answer: 起点就是答案
        return dp[0][0]
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {    
        int n = triangle.size();

        int[][] dp = new int[n][n]; // half are waste

        for (int i = 0; i < n; i++){
            dp[n-1][i] = triangle.get(n-1).get(i); // bottom line 
        }

        //botton up
        for (int i = n - 2; i > -1; i--){
            for (int j = 0; j < triangle.get(i).size(); j++){
                dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i+1][j], dp[i+1][j+1]);
            }
        }
        return dp[0][0];
    }
}

Solution 5 DP Botttom up forloop. Rolling Array to optimize space 滚动数组空间优化。 Time O(n^2) Space O(n)

class Solution:
    """
    @param triangle: a list of lists of integers
    @return: An integer, minimum path sum
    """
    def minimumTotal(self, triangle):
        n = len(triangle)
        
        # state: dp[i][j] 代表从 i,j  走到最底层的最短路径值
        dp = [[0] * n, [0] * n]
        
        # initialize: 初始化终点（最后一层）
        for i in range(n):
            dp[(n - 1) % 2][i] = triangle[n - 1][i]
            
        # function: 从下往上倒过来推导，计算每个坐标到哪儿去
        # dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
        for i in range(n - 2, -1, -1):
            for j in range(i + 1):
                dp[i % 2][j] = min(dp[(i + 1) % 2][j], dp[(i + 1) % 2][j + 1]) + triangle[i][j]
                
        # answer: 起点就是答案
        return dp[0][0]

Solution 6 DP Top-down forloop. Time O(n^2) Space O(n^2)

class Solution:
    def minimumTotal(self, triangle):
        n = len(triangle)
        
        # state: dp[i][j] 代表从 0, 0 走到 i, j 的最短路径值
        dp = [[0] * (i + 1) for i in range(n)]
        
        # initialize: 三角形的左边和右边要初始化
        # 因为他们分别没有左上角和右上角的点
        dp[0][0] = triangle[0][0]
        for i in range(1, n):
            dp[i][0] = dp[i - 1][0] + triangle[i][0]
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]
        
        # function: dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
        # i, j 这个位置是从位置 i - 1, j 或者 i - 1, j - 1 走过来的
        for i in range(2, n):
            for j in range(1, i):
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]
               
        # answer: 最后一层的任意位置都可以是路径的终点
        return min(dp[n - 1])