LeetCodeCampsDay32动态规划paro01

动态规划基础

动态规划基础

什么是动态规划

在关于贪心算法，你该了解这些！ (opens new window)中我举了一个背包问题的例子。

例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。

所以贪心解决不了动态规划的问题。

其实大家也不用死扣动规和贪心的理论区别，后面做做题目自然就知道了。

而且很多讲解动态规划的文章都会讲最优子结构啊和重叠子问题啊这些，这些东西都是教科书的上定义，晦涩难懂而且不实用。

大家知道动规是由前一个状态推导出来的，而贪心是局部直接选最优的，对于刷题来说就够用了。

动态规划的解题步骤

  1. 确定dp数组以及下标的含义
  2. 研究递推公式
  3. dp数组如何初始化
  4. 研究遍历顺序（开始下标，结束下标）
  5. 举例推导dp数组

注意，递推公式决定了如何初始化dp数组

动态规划debug

打印dp数组！

打印dp数组！

打印dp数组！

按递推公式检查dp数组初始化是否正确、以及dp的结果哪儿出错了，要和模拟推导一致！

出错可能：递归公式、初始化、遍历顺序

509. 斐波那契数

https://leetcode.cn/problems/fibonacci-number/

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1
2
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

1
2
3
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

1
2
3
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

1
2
3
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

  • 0 <= n <= 30

动态规划思路

题目比较基础，并且已经给出了递归公式F(n) = F(n - 1) + F(n - 2)

那么按动态规划的步骤来

  1. 确定dp数组以及下标含义：dp下标为输入i, dp数组的值为对应的斐波那契数数字
  2. 递推公式题目已经给了
  3. dp数组初始化：dp[0]和dp[1]题目已经给了,其它值需要动态添加（默认全为0）
  4. 遍历顺序：从下标2开始，一直到下标n（注意是下标n）而不是n-1
  5. 推导举例：dp[0]=0, dp[1]=1, dp[2] = dp[0] + dp[1] = 1, dp[3] = dp[1] + dp[2] = 2; dp[4] = dp[2] + dp[3] = 3…

动态规划代码

  • 时间复杂度O(N)
  • 空间复杂度O(N)
1
2
3
4
5
6
class Solution:
    def fib(self, n: int) -> int:
        dp = [0, 1]
        for i in range(2, n + 1):
            dp.append(dp[i - 1] + dp[i - 2])
        return dp[n]

70. 爬楼梯

https://leetcode.cn/problems/climbing-stairs/

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

1
2
3
4
5
6
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

  • 1 <= n <= 45

动态规划思路

  1. dp数组以及下标含义：下标是第i阶；dp数组值为到达第i阶有dp[i]种方法
  2. 递推公式，对于第i阶来说，只有从第i-2或第i-1台阶爬上来，所以到第i阶的方法数dp[i] = dp[i - 1] + dp[i - 2]
  3. dp初始化：dp[0]=1, dp[1]=2
  4. dp遍历顺序：从i=2开始遍历，遍历到n-1，最终返回n-1
  5. 举例推导
1
2
3
4
n=1, res=1
n=2, res=2
n=3(1+n=2, 2+n=1), res = 3
n=4(1+n=3, 2+n=2), res = 3 + 2 = 5

动态规划代码

  • 时间复杂度O(N)
  • 空间复杂度O(N)
1
2
3
4
5
6
7
8
9
class Solution:
    def climbStairs(self, n: int) -> int:

        dp = [1, 2]
        # 和FB那题目不同点是结束位置在i=n-1
        for i in range(2, n):
            dp.append(dp[i - 1] + dp[i - 2])
        # 同样返回i=n-1
        return dp[n - 1]

746. 使用最小花费爬楼梯

https://leetcode.cn/problems/min-cost-climbing-stairs/

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

1
2
3
4
5
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

1
2
3
4
5
6
7
8
9
10
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999

动态规划思路

  1. 确定dp数组以及下标含义：下标指第i层，dp[i]指爬到第i层的最低成本，注意cost[i]是指从第i层出发爬到其它层的成本
  2. 递推公式：和爬楼梯很像，想到达第i层只能靠第i-1或第i-2层爬上来，并且需要挑第i-1或第i-2层中最低成本的爬上来：dp[i] = min(cost[i-1] + dp[i-1], cost[i - 2] + dp[i - 2]); 注意cost[i-1] + dp[i-1]才是到达第i层的成本（包含了从i-1到i的成本，以及从最底层爬到第i-1层的成本
  3. dp初始化：前两层dp[0]和dp[1]为0
  4. 遍历顺序：从i=2开始遍历，结束位置为i=n(n为数组长度)，返回dp[n]
  5. 举例
1
2
3
index= [0, 1, 2,3,4, 5, 6,7, 8, 9]
cost = [1,100,1,1,1,100,1,1,100,1]
dp   = [0, 0, 1,2,2, 3, 3,4, 4, 5]

动态规划代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # dp里装着最小爬到i层的最低成本
        # dp初始化前两个台阶都为0
        dp = [0, 0]
        # 
        L = len(cost)
        # 注意题目要求是到顶楼，也就是到第L+1个（明显是超过cost长度的）
        for i in range(2, L + 1):
            # 需要判断cost[i - 1]和cost[i - 2]哪个更低
            dp.append(min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]))
        return dp[L]