代码随想录算法训练营 Day38 动态规划1

Day38 动态规划1

理论基础

动态规划题目类型

1. 动态规划基础类
2. 背包问题
3. 打家劫舍
4. 股票问题
5. 子序列问题

动态规划解题步骤

动规五部曲

1. 了解dp数组以及下标的含义
2. 递推公式
3. dp数组如何初始化
4. 遍历顺序
5. 打印dp数组

509. 斐波那契数

思路

根据题意，尝试写代码
自己写的时候，容易弄不清楚，下标应该从哪里开始，哪里结束，往往是运行出错后，发现下标不对

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

成功通过

根据代码随想录

动规五部曲步骤：

1. 确定dp数组及其下标含义；这里的dp[i]表示，第i个斐波那契数值
2. 递推公式：dp[i] = dp[i - 1] + dp[i - 2]
3. dp数组初始化 dp[0] = 1, dp[1] = 1
4. 遍历顺序，从前往后
5. 打印dp数组，用于debug

最终代码：

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        dp = [0] * (n + 1)
        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. 爬楼梯

思路

第i阶楼梯的方法，是第i-1阶的方法和第i-2阶的楼梯方法之和
因此递推公式类似于斐波那契数
dp[i]表示爬到第i个台阶，有多少种方法

尝试写代码：

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

成功通过！

746. 使用最小花费爬楼梯

思路

dp[i]的含义，爬到第i个台阶需要支付的费用
这里的递推公式为，根据cost算出从i-1个开始爬和i-2个开始爬，花费最少的费用

尝试写代码：

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

成功通过！