动态规划学习_dp数组

1.简介

动态规划一般用来解决最值问题，动态规划核心问题是穷举，因为要求最值，所以将所以可能列出来，然后求最值。动态规划的难点在于如何穷举，即写状态转移方程。
写状态转移方程的思路：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。参见此篇文章。

状态：dp函数的参数，或者dp数组的索引（可根据dp数组定义，自己做题感觉，第一步先定义dp数组，这样也有助于找到状态）

解题框架如下：

# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. leetcode题目

509. 斐波那契数
解法一：带备忘录的递归(自顶向下，从n->0，看helper函数)

class Solution:
    def __init__(self):
        self.record = {}

    def fib(self, n: int) -> int:
        if n == 0 or n == 1:
            return n
        if n in self.record:
            return self.record[n]
        self.record[n] = self.fib(n-1) + self.fib(n-2)
        return self.record[n]
1
2
3
4
5
6
7
8
9
10
11

解法二：迭代（自底向上， 从0-n）

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        dp = [0] * (n + 1)
        # base case
        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
2
3
4
5
6
7
8
9
10
11
12

322. 零钱兑换
以下的分析来自参考文章。
1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。

2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。

3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。

4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。
所以我们可以这样定义 dp 函数：dp(n) 表示，输入一个目标金额 n，返回凑出目标金额 n 所需的最少硬币数量。

状态转移方程如下图：

通过的代码如下，采取备忘录的形式，自顶向下。

class Solution:
    """
    https://labuladong.github.io/algo/1/7/
    """

    def coinChange(self, coins: List[int], amount: int) -> int:
        # 备忘录初始化为一个不会被取到的特殊值，代表还未被计算
        memo = [-666] * (amount + 1)

        def dp(coins, amount):
            if amount == 0:
                return 0
            if amount < 0:
                return -1
            # 查备忘录，防止重复计算
            if memo[amount] != -666:
                return memo[amount]
            ans = amount + 1
            for coin in coins:
                # 计算子问题的结果
                count = dp(coins, amount - coin)
                # 子问题无解则跳过
                if count == -1:
                    continue
                # 在子问题中选择最优解，然后加一
                ans = min(ans, count + 1)
            # 把计算结果存入备忘录
            memo[amount] = -1 if ans == amount + 1 else ans
            return memo[amount]

        return dp(coins, amount)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

自底向上方式：
dp 函数体现在函数参数，而 dp 数组体现在数组索引。
dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。

class Solution:
    """
    https://labuladong.github.io/algo/1/7/
    自底向上
    """
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for i in range(amount + 1):
            for coin in coins:
                if i - coin < 0:
                    continue
                dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[amount] if dp[amount] != amount + 1 else -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

300. 最长递增子序列
首先定义好dp数组，写状态转移方程：使用数学归纳法，假设dp[0,1…i-1]已知道，求dp[i]。

总结一下如何找到动态规划的状态转移关系：
1、明确 dp数组的定义。这一步对于任何动态规划问题都很重要，如果不得当或者不够清晰，会阻碍之后的步骤。

2、根据 dp 数组的定义，运用数学归纳法的思想，假设 dp[0…i-1] 都已知，想办法求出 dp[i]，一旦这一步完成，整个题目基本就解决了。但如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组。

class Solution:
    """
    https://labuladong.github.io/algo/3/26/76/
    写状态转移方程：使用数学归纳法，假设dp[0,1...i-1]已知道，求dp[i]
    """

    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        # dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
        # base case：dp 数组全都初始化为 1
        dp = [1] * (n + 1)
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], 1 + dp[j])
        return max(dp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

53. 最大子数组和

定义: dp[i]表示以nums[i]结尾的最大子数组和。

像子数组、子序列这类问题，你就可以尝试定义 dp[i] 是以 nums[i] 为结尾的最大子数组和/最长递增子序列，因为这样定义更容易将dp[i+1] 和 dp[i] 建立起联系，

class Solution:
    """
    动态规划
    """

    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        # 定义: dp[i]表示以nums[i]结尾的最大子数组和
        dp = [0] * n
        # base case
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(nums[i], dp[i - 1] + nums[i])
        return max(dp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

0-1背包问题

学习labuladong讲的0-1背包问题
题目：

解法思路：




学习链接：https://www.bilibili.com/video/BV15B4y1P7X7/?spm_id_from=333.788&vd_source=0bb27f41a15b7647692098b1b9dcf21b

参考

动态规划解题套路框架