动态规划相关：三角形最小路径和

一、爬楼梯

1、自顶向下

memo = {
    1:1, 2:2}
class Solution:
    def climbStairs(self, n: int) -> int:
    	# dp 自顶向下 -> 记忆化递归
        if n not in memo:
            memo[n] = self.climbStairs(n - 1) + self.climbStairs(n - 2)
        return memo[n]

2、自底向上

class Solution:
    def climbStairs(self, n: int) -> int:
        # dp 自底向上
        if n == 1: return 1
        dp = [0 for _ in range(n+1)]
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
        	# dp列表你可以认为它主要用途，是为了得到最后结果，用来存储中间结果
            dp[i] = dp[i-1]+dp[i-2] # 递推公式，或叫dp方程、状态转移方程
        return dp[n]

下面我们来 优化内存，上面用了列表！其目的是为了得到最后结果，用来存储中间结果，其实本题而言我们暂存dp[i-1]、dp[i-2]两个值即可，不断向后迭代更新这两个值！

class Solution:
    def climbStairs(self, n: int) -> int:
        # dp 自底向下：本质循环--即迭代法
        if n <= 3: return n
        a, b = 2, 3 # 计算我们从第四阶计算走即可！四阶前面都是ret n
        for _ in range(n-3):
            a, b = b, a + b
        return b

二、三角形最小路径和

1、自顶向下

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # dp 自顶向下
        dp = [[0 for _ in range(i+1)] for i in range(len(triangle))]
        def dfs(i,j):
            if i >= len(triangle):
                return 0
            if not dp[i][j]:
                sub1 = dfs(i+1,j)
                sub2 = dfs(i+1,j+1)
                dp[i][j] = min(sub1, sub2)+triangle[i][j]
            return dp[i][j]
        return dfs(0,0)

2、自底向上

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = triangle
        # 最后一排不用遍历,且索引等于长度-1，所以len(triangle) - 2
        for i in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[i])):
                dp[i][j] += min(dp[i+1][j],dp[i+1][j+1])
        return dp[0][0]

四、编辑距离

1、自顶向下

2、自底向上

五、最长有效括号

1、自顶向下

2、自底向上

六、最小路径和

1、自顶向下

2、自底向上

七、解码方法

1、自顶向下

2、自底向上

八、最大正方形

1、自顶向下

2、自底向上

九、矩形区域不超过K的最大数值和

1、自顶向下

2、自底向上

十、青蛙过河

1、自顶向下

2、自底向上

十一、分割数组的最大值

1、自顶向下

2、自底向上

十二、学生出勤记录II

1、自顶向下

2、自底向上

十三、任务调度器

1、自顶向下

2、自底向上

十四、戳气球

1、自顶向下

2、自底向上