120. 三角形最小路径和(Medium)

Python

DFS 方法

# timeout 42/43
import math 
class Solution:
    ans = math.inf
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        def dfs(i, j, s):
            if i == len(triangle):
                self.ans = min(self.ans, s)
                return 
            dfs(i + 1, j, s + triangle[i][j])
            dfs(i + 1, j + 1, s + triangle[i][j])
        dfs(0, 0, 0)
        return self.ans 

分治算法

# timeout 42/43
import math 
class Solution:
    ans = math.inf
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        def dfs(i, j):
            if i == len(triangle): return 0
            return min(dfs(i + 1, j), dfs(i + 1, j + 1)) + triangle[i][j]
        return dfs(0, 0)

记忆化的分治

import math 
class Solution:
    ans = math.inf
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        def dfs(i, j):
            if (i, j) in memo: return memo[(i, j)]
            if i == len(triangle): return 0
            res = min(dfs(i + 1, j), dfs(i + 1, j + 1)) + triangle[i][j]
            memo[(i, j)] = res 
            return res 
        memo = dict()
        return dfs(0, 0)

动态规划

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        if not n: return 0 
        dp = [[0] * n for _ in range(n)]
        dp[0][0] = triangle[0][0]
        for i in range(1, n):
            dp[i][0] = dp[i - 1][0] + triangle[i][0]
            for j in range(1, len(triangle[i]) - 1):
                a = dp[i - 1][j] 
                b = dp[i - 1][j - 1]
                dp[i][j] = min(a, b) + triangle[i][j]
            dp[i][len(triangle[i]) - 1] = dp[i - 1][len(triangle[i]) - 2] + \
                                          triangle[i][len(triangle[i]) - 1]
        return min(dp[n - 1])

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func minimumTotal(triangle [][]int) int {
    if len(triangle) == 0 || len(triangle[0]) == 0 { // 空数组
        return 0
    }
    n := len(triangle)
    dp := make([][]int, n)
    for i:= 0; i < n; i++ {
        dp[i] = make([]int, len(triangle[i]))
    }
    dp[0][0] = triangle[0][0]

    for i := 1; i < n; i++ {
        dp[i][0] = dp[i - 1][0] + triangle[i][0]
        for j := 1; j < len(triangle[i]) - 1; j++ {
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]
        }
        dp[i][len(triangle[i]) - 1] = dp[i - 1][len(triangle[i]) - 2] + 
                                      triangle[i][len(triangle[i]) - 1]
    }

    ans := dp[n - 1][0]
    for _, v := range dp[n - 1] {
        if v < ans {
            ans = v 
        }
    }
    
    return ans 
}