动态规划-动归基础

分类：动规基础、背包问题、打家劫舍、股票问题、子序列问题

动规由上一个状态推导出来，而贪心是局部选最优

解题步骤：
1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序

5. 举例推导dp数组

509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

解题步骤：
1. 确定dp数组（dp table）以及下标的含义：dp[i]-第i个斐波那契数的值
2. 确定递推公式：dp[i] = dp[i-1]+dp[i-2]
3. dp数组如何初始化: dp[0]=0，dp[1]=1
4. 确定遍历顺序: 从前向后

5. 举例推导dp数组

dp数组大小为（n+1）：dp[2]需要存储dp[0]\dp[1]\dp[2]

class Solution:
    def fib(self, n: int) -> int:
       
        # 排除 Corner Case
        if n == 0:
            return 0
        
        # 创建 dp table 
        dp = [0] * (n + 1)

        # 初始化 dp 数组
        dp[0] = 0
        dp[1] = 1

        # 遍历顺序: 由前向后。因为后面要用到前面的状态
        for i in range(2, n + 1):

            # 确定递归公式/状态转移公式
            dp[i] = dp[i - 1] + dp[i - 2]
        
        # 返回答案
        return dp[n]

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

迈到第n阶：从n-1阶迈一步/从n-2阶迈两步--n-1阶的方法数+n-2阶的方法数

解题步骤：
1. 确定dp数组（dp table）以及下标的含义： dp[i]: 迈到第i阶有dp[i]种方法
2. 确定递推公式：dp[i] = dp[i-1]+dp[i-2]
3. dp数组如何初始化：dp[1] = 1, dp[2] = 2
4. 确定遍历顺序：从前向后

5. 举例推导dp数组

⚠️注意初始化：dp[1] =1 dp[2]=2，那么就需要在前面增加n=1和n=2时的返回值

class Solution:
    def climbStairs(self, n: int) -> int:
        #边界条件
        if n == 1:
            return 1
        if n == 2:
            return 2
        # 创建dp table
        dp = [0]*(n+1) #n个数
        #初始化
        dp [1] = 1
        dp [2] = 2
        for i in range(3,n+1):
            #递推公式
            dp [i] = dp[i-1]+dp[i-2]
        return dp[n]

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

解题步骤：
1. 确定dp数组（dp table）以及下标的含义 dp[i]: 到达下标i的位置的最小花费dp[i]
2. 确定递推公式：dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
3. dp数组如何初始化：dp [0] = 0, dp[1]=0 （不向上爬前无需支付；你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯）
4. 确定遍历顺序：从前向后

5. 举例推导dp数组

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0]*(n+1)
        dp [0]= 0 #可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯,向上爬前无需支付费用
        dp [1]= 0
        for i in range(2, n+1):
            dp [i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
        return dp[n]

62. 不同路径 （多维）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

1. 确定dp数组（dp table）以及下标的含义：到达[i][j]位置有dp[i][j]条路径
2. 确定递推公式：dp[i][j] = dp[i-1][j]+dp[i][j-1]
3. dp数组如何初始化：dp[0][j] =1, dp[i][0]=1
4. 确定遍历顺序：从左往右，从上往下

5. 举例推导dp数组

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1 for i in range(n)]for j in range(m)]
#没有障碍物 内部初始化为1也是可以的
        for i in range(1,m):
            for j in range(1,n):
                #dp [0][j]=1
                #dp [i][0]=1
                dp[i][j] = dp[i-1][j]+dp[i][j-1]
        return dp[m-1][n-1]

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

1. 确定dp数组（dp table）以及下标的含义：dp[i][j]是移动到规定位置的不同路径数
2. 确定递推公式：dp[i][j]=dp[i-1][j]+dp[i][j-1] （if obstacleGrid[i][j]==0:# 如果没有障碍 ）
3. dp数组如何初始化:第1行/列无障碍时dp[i][0] = 1, dp[0][j] = 1 有障碍-他的后面/下面都置0
4. 确定遍历顺序: 从上至下，从左往右

5. 举例推导dp数组

dp 表在初始化时所有值都设为 0，意味着在这些位置上没有路径

• 如果 obstacleGrid[i][j] 是 1（障碍物），则 dp[i][j] 会保持为 0。
• 如果 obstacleGrid[i][j] 是 0，则 dp[i][j] 会根据上方和左方的路径数更新。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        #创建dp table
        row = len(obstacleGrid) # 行数
        col = len(obstacleGrid[0]) #列数
        dp =[[0 for _ in range(col)]for _ in range(row)]#[[列数）]行数]
        #边界条件:障碍在起点或终点
        if obstacleGrid[0][0] == 1 or obstacleGrid[row-1][col-1]==1:
            return 0
        #初始化第一行
        for j in range(col):
            if obstacleGrid[0][j] == 1:#遇到障碍后 后面的值都置0
                break
            dp [0][j] = 1 
        #初始化第一列
        for i in range(row):
            if obstacleGrid[i][0] == 1:#遇到障碍后 后面的值都置0
                break
            dp[i][0] = 1
        #动规函数
        for i in range(1,row): #动i，遍历第一列，范围应该是(1,行数)
            for j in range(1,col):#遍历行
                if obstacleGrid[i][j]==0:# 如果没有障碍
                    dp[i][j] = dp[i-1][j]+dp[i][j-1]
        return dp[row-1][col-1]

✅⚠️ 二维数组的输入：

row1 = input().strip().split()
row2 = input().strip().split()
row3 = input().strip().split()
obstacleGrid = []
obstacleGrid.append(list(map(int,row1)))
obstacleGrid.append(list(map(int,row2)))
obstacleGrid.append(list(map(int,row3)))

343. 整数拆分（难）

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

可以从1遍历j，然后有两种渠道得到dp[i]:一个是j * (i - j) 直接相乘, 一个是j * dp[i - j]，相当于是拆分(i - j)。j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。dp[i]=dp[j]*dp[i-j]至少得拆成4个数所以x

为什么还要比较dp[i]呢？在递推公式推导的过程中，每次计算dp[i]，取最大的而已。

1. 确定dp数组（dp table）以及下标的含义：dp[i]对i进行拆分，拆分后的最大乘积
2. 确定递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j})-- j从1开始遍历，在dp[i-j]里被拆过
3. dp数组如何初始化：dp[2]=1
4. 确定遍历顺序: i从3开始遍历到后，j从1到i

5. 举例推导dp数组

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0 for _ in range(n+1)] #创建dp table
        dp[2] = 1  #初始化
        for i in range(3,n+1): #遍历顺序
            for j in range(1,i):
                dp[i] =max(j*(i-j), j * dp[i-j], dp[i])
        return dp[n]

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

1. 确定dp数组（dp table）以及下标的含义
dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。

2. 确定递推公式

dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

3. dp数组如何初始化: dp[0] = 1

4. 确定遍历顺序

节点数为i的状态是依靠 i之前节点数的状态。

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