动态规划-动归基础
分类:动规基础、背包问题、打家劫舍、股票问题、子序列问题
动规由上一个状态推导出来,而贪心是局部选最优
解题步骤:
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到i5. 举例推导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]