【动态规划】LeetCode刷题清单及思路记录

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 n
        else:
            dp=[0]*(n+1)
            dp[1]=1
            for 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]=1
        for 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]
从这两种方案中，采用花费小的那种方案，
故，状态转移方程为：
$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]

62 不同路径

LeetCode 题目链接

63 不同路径Ⅱ

LeetCode 题目链接

343 整数拆分

LeetCode 题目链接

96 不同的二叉搜索树

LeetCode 题目链接

（背包问题：0-1背包和完全背包）

416 分割等和子集

LeetCode 题目链接

1049 最后一块石头的重Ⅱ

LeetCode 题目链接

494 目标和

LeetCode 题目链接

474 一和零

LeetCode 题目链接

518 零钱兑换Ⅱ

LeetCode 题目链接

377 组合总和Ⅳ

LeetCode 题目链接

70 爬楼梯

LeetCode 题目链接

322 零钱兑换

LeetCode 题目链接

279 完全平方数

LeetCode 题目链接