343. 整数拆分

• 思路
  • example

i = 1 + (i-1) = 2 + (i-2) = ...
,
i = j + (i-j) 最后一个数字为j. 之前的和为i-j (分为两种情况：i-j可分为>=2个数字之和；i-j是单独数字）

• 复杂度. 时间：, 空间:

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0 for _ in range(n+1)]
        dp[2] = 1
        for i in range(3, n+1):
            for j in range(1, i):
                dp[i] = max(dp[i], dp[i-j]*j, (i-j)*j) 
                #                至少三数积      两数积
        return dp[n]

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0 for _ in range(n+1)]
        dp[1] = 1
        dp[2] = 1
        for i in range(3, n+1):
            for j in range(1, i): 
                dp[i] = max(dp[i], j*(i-j), j*dp[i-j]) 
        return dp[n]

• 方法
  subject to
  max. occurs when .
  
  
  , log technique
  max. occurs when . Since is an integer, compare with , conclude is the best choice.

n = 3a + b
b = 0:
b = 1: b = 2:

class Solution:
    def integerBreak(self, n: int) -> int:
        if n <= 3: return n - 1
        a, b = n // 3, n % 3
        if b == 0: return int(math.pow(3, a))
        if b == 1: return int(math.pow(3, a - 1) * 4)
        return int(math.pow(3, a) * 2)

96. 不同的二叉搜索树

• 思路
  • example
  • 返回满足题意的二叉搜索树的种数。不需要找到具体的方案。
  • DP 问题转化！
    • dp[i]:　节点1,..., i 能组成的不同BST的个数
    • dp[i] += dp[i-j]*dp[j-1] for j in range(1, i) 取j为头节点 (左子树：1,...,j-1; 右子树：j+1,...,i)

1, 2, 3, ..., j-1, j, j+1, ..., i，
节点j为头节点，左边j-1个（连续）数，右边i-j个（连续）数

• 复杂度. 时间：, 空间:

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n+1):
            for j in range(1, i+1):
                dp[i] += dp[j-1] * dp[i-j]
        return dp[n]

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n+1):
            for j in range(1, i+1):
                dp[i] += dp[j-1]*dp[i-j] 
        return dp[n]

931. Minimum Falling Path Sum

• 思路
  • example

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0]) # notice that here m = n
        dp = [[0 for _ in range(n)] for _ in range(m)]
        dp[0] = matrix[0]
        for i in range(1, m):
            for j in range(n):
                if j == 0:
                    dp[i][j] = min(dp[i-1][j], dp[i-1][j+1]) + matrix[i][j]
                elif j == n-1:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + matrix[i][j]
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i][j]
        return min(dp[m-1])

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])  
        dp = [[float('inf') for _ in range(n)] for _ in range(m)] 
        for j in range(n):
            dp[0][j] = matrix[0][j] 
        for i in range(1, m):
            for j in range(n):
                if j > 0:
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]+matrix[i][j]) 
                if j < m-1:
                    dp[i][j] = min(dp[i][j], dp[i-1][j+1]+matrix[i][j]) 
                dp[i][j] = min(dp[i][j], dp[i-1][j]+matrix[i][j]) 
        return min(dp[m-1])