动态规划

思路:动态规划五步曲

1.确定dp[i]的含义
2.确定递推公式
3.dp数组初始化
4.确定dp数组遍历顺序
5.打印dp数组(查错)

例题

class Solution:
    def fib(self, n: int) -> int:
        if n==0 or n==1:
            return n
        f0,f1=0,1
        for i in range(2,n+1):
            sum=f0+f1
            f0=f1
            f1=sum
        return f1

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

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n=len(cost)
        if n==2:
            return min(cost[0],cost[1])
        f0=f1=0
        for i in range(2,n+1):
            minima=min(f0+cost[i-2],f1+cost[i-1])
            f0=f1
            f1=minima
        return f1

class Solution(object):
    def uniquePaths(self, m, n):
        d = {}
        def dfs(i, j):
            # 如果(i,j)在缓存中则直接返回
            if (i, j) in d:
                return d[i,j]
            # 到达边界时，返回 1    
            if i == m - 1 or j == n - 1:
                return 1
            # 继续递归调用，往下i+1，往右j+1    
            d[i,j] = dfs(i + 1, j) + dfs(i, j + 1)
            return d[i,j]
        return dfs(0,0)

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # 1.确定dp及下标的含义 
        # 二维数组，每个元素表示到达当前位置的不同路径的个数
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [[0]*n for _ in range(m)]
        # 3. 确定dp数组如何初始化
        for row in range(len(obstacleGrid)):
            # 遇到障碍，后续不通，值为默认0
            if obstacleGrid[row][0] == 1:
                break
            dp[row][0] = 1
        for col in range(len(obstacleGrid[0])):
            if obstacleGrid[0][col] == 1:
                break
            dp[0][col] = 1
        # 4. 确定遍历顺序
        for row in range(1,m):
            for col in range(1, n):
                # 2.确定递推公式
                # 只能向下或向右移动，则当前位置只能是上边和左边的不同路径之和
                if obstacleGrid[row][col] == 1:
                    continue
                dp[row][col] = dp[row-1][col] + dp[row][col-1] 
        # print(dp)
        return dp[-1][-1]

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