失眠网 > 【LeetCode刷题】动态规划相关题目（附Python代码）

【LeetCode刷题】动态规划相关题目（附Python代码）

时间：2022-11-01 09:02:54

文章目录

509 斐波那契数列70 爬楼梯朴素的思路：从状态转移入手完全背包的思路：从走法入手 746 使用最小花费爬楼梯62 不同路径63 不同路径Ⅱ343 整数拆分96 不同的二叉搜索树（背包问题：0-1背包和完全背包）416 分割等和子集1049 最后一块石头的重Ⅱ494 目标和474 一和零518 零钱兑换Ⅱ377 组合总和Ⅳ70 爬楼梯322 零钱兑换279 完全平方数

509 斐波那契数列

LeetCode 题目链接

动态规划的本质就是用空间换时间

这是个入门的动态规划题，状态清晰，状态转移方程明确

状态：dp[i] ：数列的第 i 个数状态转移方程：dp[i]=dp[i-1]+dp[i-2]初始状态：dp[0]=0, dp[1]=1

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

70 爬楼梯

LeetCode 题目链接

这个题有两种思路：

朴素的思路：从状态转移入手

爬到第 i 级台阶有两种方式：

1.从第 i-1 级爬一级台阶

2.从第 i-2 级爬两级台阶

所以，定义 :

状态：dp[i] 为爬到第 i 级台阶的方法数状态转移方程：dp[i]=dp[i-1]+dp[i-1]初始状态：dp[0]=1,dp[1]=1

注：这个题和斐波那契数列很像，但注意看 dp[2]=2，即，初始状态 dp[0]=1。

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

完全背包的思路：从走法入手

这个思路开始有点做应用题的意思了，重新审题，走法有两种：走一步和走两步，目的是走到第n级台阶上。

换种表达方式，即用 1 和 2 的步数加和，凑到 n 这个数，记录方法数。这不就是完全背包嘛。

直接上代码：

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

746 使用最小花费爬楼梯

LeetCode 题目链接

这个题也不太费脑，题目直接给出了明确的状态定义和状态转移路径。但与前几个题目不同的是，这里记录的不再是到达第n级台阶的方法数，这里记录的是最小花费。因此，本题的难点在状态转移方程：

爬到第 i 级台阶有两种方案，其花费分别为：

1.从第 i-1 级爬上来其花费是 dp[i-1]+cost[i-1]

2.从第 i-2 级爬上来其花费是 dp[i-2]+cost[i-2]

从这两种方案中，采用花费小的那种方案，

故，状态转移方程为：

d p [ i ] = m i n ( d p [ i − 1 ] + c o s t [ i − 1 ] , d p [ i − 2 ] + c o s t [ i − 2 ] ) dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]) dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:n=len(cost)dp=[0]*(n+1) 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]