算法记录 | Day38 动态规划-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法记录 | Day38 动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

对于动态规划问题，将拆解为如下五步曲

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

509.斐波那契数

思路：

确定dp数组（dp table）以及下标的含义：dp[i]的定义为：第i个数的斐波那契数值是dp[i]
确定递推公式：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]
dp数组如何初始化：dp[0] = 0，dp[1] = 1
确定遍历顺序：从前到后遍历
举例推导dp数组：推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

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

思路：

确定dp数组（dp table）以及下标的含义：dp[i]：爬到第i层楼梯，有dp[i]种方法
确定递推公式：

dp[i] 可以有两个方向推出来。

首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
dp数组如何初始化：dp[0] = 1，dp[1] = 1
确定遍历顺序：从前到后遍历
举例推导dp数组：

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

746.使用最小花费爬楼梯

思路：

确定dp数组（dp table）以及下标的含义：dp[i]爬到楼顶的花费
确定递推公式：

dp[i - 1]，到上i-1层楼梯，花费dp[i - 1]，i-1到i花费dp[i - 1]+cost[i-1]

dp[i - 2]，上i-2层楼梯，花费dp[i - 2]，i-2到i花费dp[i - 2]+cost[i-2]

dp [i] = min(dp[i - 1]+cost[i-1]，dp[i - 2]+cost[i-2])
dp数组如何初始化：dp[0] = 0，dp[1] = 0

**注意：**题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说从到达第 0 个台阶是不花费的，但从第0 个台阶往上跳的话，需要花费 cost[0]。
确定遍历顺序：从前到后遍历
举例推导dp数组：

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：

算法记录 | Day38 动态规划文章来源地址https://www.toymoban.com/news/detail-421340.html

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