120. Triangle

Key idea: memorize search＋from bottom to top

核心：记忆搜索＋自底而上

List<List<Integer>> triangle actual shape

(0,0) -> (1,0), (1,1)

(1,0) -> (2,0), (2,1) ; (1,1) -> (2,1), (2,2) ;

(2,0) -> (3,0), (3,1) ; (2,1) -> (3,1), (3,2) ; (2,2) -> (3,2), (3,3) ;

........

According to above, (2,1) (3,1) (3,2) are repeated. If do regular DFS, every node has 2 choices, left or right in the next row. Therefore, time complexity is $O(2^n)$ . So another method is to store all the minimal path from any node to the last row. We let dfs(int x, int y) records the minimal path sum from (x,y) to the last row.

sumPath[x][y] = min(dfs(x+1, y),dfs(x+1, y+1)) + traingle[x][y]

Space complexity is $O(n^2)$ (sumPath[][]). Because every node is only needed to compute once, there are $(n(n+1))/2$ times of computation, if every computation is $O(1)$ , then time complexity is $O(n^2)$

If we do from bottom to up to record the minimal path for each node, we only need a int[] minPath to store the minimal path for each node of next row. Then taking advantage of minPath[] infers the minimal path of each node in current row. The result is minPath[0][0]. The space complexity is $O(n)$ , the time complexity is $O(n^2)$

Deciding which part of the cache to discard to save space can be a hard job.

此题关键是，dfs记录当前状态到达目标状态的耗费，记忆化搜索就是dfs带值回来。

不仅要做DFS，还要自下而上方便存储，并且每次DFS要带值回来，dfs(x,y)即从（x,y）到终点的最短路径。

求最值一般可以用动态规划实现，而不是列举所有可能性。动态规划的精髓是记忆化搜索，记忆化搜索的精髓是自底而上，值可以被重复利用。

English

DP is memorize search

Advantage: easy to think and implement

Disadvantage: Expensive memory cost

Chinese

动态规划的本质是记忆化搜索

优点：容易想到并实现

缺点：耗费存储空间

Iterative

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        miniPath = [[0] * len(triangle[-1])] * len(triangle)
        for i in range(len(triangle[-1])):
            miniPath[-1][i] = triangle[-1][i]
            
        for i in reversed(range(len(triangle)-1)):
            for j in range(len(triangle[i])):
                miniPath[i][j] = min(miniPath[i+1][j], miniPath[i+1][j+1]) + triangle[i][j]
        
        print(miniPath)
        return miniPath[0][0]

Recursive

class Solution:    
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # edge case
        if len(triangle) == 0:
            return 0
        elif len(triangle) == 1:
            return triangle[0][0]

        l = len(triangle)
        sumPath = [[-1]*l for i in range(l)]
        return self.dfs(triangle, 0, 0, sumPath)
    
    def dfs(self, triangle, x, y, sumPath):
        # stop condition
        if x == len(triangle):
            return 0
        
        # regular case
        if sumPath[x][y] == -1:
            left = self.dfs(triangle,x+1,y, sumPath)
            right = self.dfs(triangle,x+1,y+1, sumPath)
            sumPath[x][y] = triangle[x][y] + min(left, right)

        return sumPath[x][y]

Python example 2: space complex = $O(n)$

Java(T=O(n))

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for(int i = triangle.size() - 2; i >= 0; i --)
            for(int j = triangle.get(i).size() - 1; j >= 0; j --) {
                int value = triangle.get(i).get(j) + Math.min(triangle.get(i+1).get(j), triangle.get(i+1).get(j+1));
                triangle.get(i).set(j, value);
            }
        return triangle.get(0).get(0);
    }
}

Python(T=O(n), S=O(n))

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        miniPath = []
        for i in range(len(triangle[-1])):
            miniPath.append(triangle[-1][i])
            
        for i in reversed(range(len(triangle)-1)):
            for j in range(0, i+1):
                miniPath[j] = min(miniPath[j], miniPath[j+1]) + triangle[i][j]
                
        return miniPath[0]

自下而上用一个list记录每一行(x,y)的最小值，每一行迭代一次，都更新目前行的每个数据的最小值。