【算法】动态规划：从斐波那契数列到背包标题

【算法】动态规划：从斐波那契数列到背包标题



1.斐波那契数列

斐波那契数列（Fibonacci sequence）是一个非常著名的数列，在数学中有着广泛的应用。这个数列的每一项都是前两项的和，通常从1开始。数列的前几项是如许的：
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
数学上，斐波那契数列可以界说为如下递归情势：
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)，对于 n ≥ 2 的整数。
依据这个递推式，我们将我们想要求的F(n)转换为求F(n-1)与F(n-2)的值，这就是动态规划中的状态转移方程。简单来说，F(n)的得来是由F(n-1)与F(n-2)决定的。
那么F(n-1)与F(n-2)从何而来呢？
我们可以将它先盘算好，存起来，用的时间直接拿来用就行。
这就是动态规划中的影象化：
通过将已经盘算过的子标题的结果存储起来，当再次碰到类似的子标题时，可以直接利用存储的结果，从而节流盘算时间和资源。
以是怎样用动态规划来求出F(n)呢？
动态规划有三大步：

• 界说子标题
  
• 界说状态数组dp
  
• 界说状态转移方程
  

我们有dp来代表F(i)的值
起首我们必要初始化dp数组：

1. dp=[0]*(n+1)

复制代码

然后我们先预处置惩罚一些值：

1. dp[1],dp[2]=1,1

复制代码

如许之后，我们就可以得出dp[3]：
dp[3]=dp[2]+dp[1]
以此类推……
我们用一个for循环就都可以表现出来：

1. for i in range(3,n+1):
2.     dp[i]=dp[i-1]+dp[i-2]

复制代码

末了dp[n]就是我们要求的值了。
完备代码:

1. def fibonacci(n):
2.     if n <= 1:return n
3.     dp = [0] * (n + 1)
4.     dp[1],dp[2] = 1,1
5.     for i in range(3, n + 1):
6.         dp[i] = dp[i - 1] + dp[i - 2]
7.     return dp[n]

复制代码

2.爬楼梯

相识这些之后，就可以做一些动态规划的标题了
而力扣的70. 爬楼梯与斐波那契数列非常相似
标题：
假设你正在爬楼梯。必要 n 阶你才气到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种差别的方法可以爬到楼顶呢？
示例 1：

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

复制代码

示例 2：

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

复制代码

提示：

• 1 <= n <= 45
  

该题中，我们只能爬1阶或2阶，求爬到楼顶的方法数
那么起首我们想到该怎样爬到楼顶
我们可以在离楼顶差一阶的时间再走1阶，差两阶的时间再走2阶。
由于本题要求爬到楼顶的方法数，以是我们可以界说子标题：求楼梯阶数为i时，我们爬到楼顶所需的方法数。
依据子标题，我们可以界说状态数组：
用dp来表现当楼梯阶数为i时，我们爬到楼顶所需的方法数。
而我们又知道：
i是由i-1再走1阶大概i-2再走2阶而来。
以是dp（楼梯阶数为i时的方法数）就即是dp[i-1]（楼梯阶数为i-1时的方法数）加上dp[i-2]（楼梯阶数为i-2时的方法数）
以是我们就可以得出状态转移方程：
dp=dp[i-1]+dp[i-2]
是不是很认识？
没错，这和斐波那契数列的状态转移方程千篇一律
不外区别在于预处置惩罚的值差别：

1. dp[1],dp[2]=1,2

复制代码

以是这道题也就办理了：

1. class Solution(object):    def climbStairs(self, n):        """        :type n: int        :rtype: int        """        if n<=1:return n        dp=[0]*(n+1)
2.         dp[1],dp[2]=1,2
3.         for i in range(3,n+1):            dp[i]=dp[i-1]+dp[i-2]        return dp[n]

复制代码

思索一：该题中的dp=dp[i-1]+dp[i-2]为什么是准确的？
我们将这题升级以下，可爬的门路数是不确定的，放在一个数组stairs中，那么代码可以如许写：

1. class Solution(object):    def climbStairs(self, n):        """        :type n: int        :type stairs: List[int]        :rtype: int        """        dp=[0]*(n+1)
2.         dp[0]=1        for i in range(1,n+1):            for j in stairs:                if i-j>=0:dp[i]+=dp[i-j]        return dp[n]

复制代码

提示:假如感觉有点难明白请先看下一题
3.零钱转换

接下来我们上升难度，力扣第332题：322. 零钱兑换
标题：
给你一个整数数组 coins ，表现差别面额的硬币；以及一个整数 amount ，表现总金额。
盘算并返回可以凑成总金额所需的 最少的硬币个数 。假如没有任何一种硬币组合能构成总金额，返回 -1 。
你可以以为每种硬币的数量是无穷的。
示例 1：

1. 输入：coins = [1, 2, 5], amount = 11
2. 输出：3
3. 解释：11 = 5 + 5 + 1

复制代码

示例 2：

1. 输入：coins = [2], amount = 3
2. 输出：-1

复制代码

示例 3：

1. 输入：coins = [1], amount = 0
2. 输出：0

复制代码

提示：

• 1 <= coins.length <= 12
  
• 1 <= coins <= 231 - 1
  
• 0 <= amount <= 104
  

本题和爬楼梯一题及其相似
我们可以将两题对比着来写：
将该题中的amount类比于爬楼梯中的n（楼梯的阶数）；将题中的coins类比于可以爬的门路数1、2
只不外这题的coins不是给定的1、2,而是随机的而已。
我们设dp表现当总金额为i时凑成总金额所需的 最少的硬币个数。
我们以coins = [1, 2, 5], amount = 11为例，我们知道，硬币就1，2，5这三种，以是当总金额为i时的最少硬币个数的得来就有三种环境：
dp[i-1]时再来拼集面值1的硬币；
dp[i-2]时再来拼集面值2的硬币；
dp[i-5]时再来拼集面值5的硬币
如图所示：

以是就能得出递推式：
dp=min(dp[i-coin]+1,dp)
coin代表的就是硬币的面值
我们的coins[1,2,5]就相当于爬楼梯中我们一次能爬的门路的阶数[1,2]
只不外爬楼梯是给定的[1,2]，而本题在变革而已，写代码时，只要注意捕获coins的变革就行了
Python代码

1. class Solution(object):
2.     def coinChange(self, coins, amount):
3.         """
4.         :type coins: List[int]
5.         :type amount: int
6.         :rtype: int
7.         """
8.         dp=[float('inf')]*(amount+1)  # 初始化dp
9.         dp[0]=0
10.         for i in range(1,amount+1):
11.             for j in coins:           # j代表硬币的面值，由于coins的不确定性，所以得增加一个for来捕获coin(每个硬币的面值)
12.                 if i-j>=0:            # 检验总额是否大于硬币面值
13.                     dp[i]=min(dp[i-j]+1,dp[i]) # 如果大于，才能就行递推
14.         return dp[-1]
15. if dp[-1] != float('inf') else -1

复制代码

思索二：在这一题中你是否看到背包标题的影子?
4.零钱兑换 II

接下来看力扣的第518题：518. 零钱兑换 II
标题：
给你一个整数数组 coins 表现差别面额的硬币，另给一个整数 amount 表现总金额。
请你盘算并返回可以凑成总金额的硬币组合数。假如任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无穷个。
标题数据包管结果符合 32 位带符号整数。
示例 1：

1. 输入：amount = 5, coins = [1, 2, 5]
2. 输出：4
3. 解释：有四种方式可以凑成总金额：
4. 5=5
5. 5=2+2+1
6. 5=2+1+1+1
7. 5=1+1+1+1+1

复制代码

示例 2：

1. 输入：amount = 3, coins = [2]
2. 输出：0
3. 解释：只用面额 2 的硬币不能凑成总金额 3 。

复制代码

示例 3：

1. 输入：amount = 10, coins = [10]
2. 输出：1

复制代码

提示：

• 1 <= coins.length <= 300
  
• 1 <= coins <= 5000
  
• coins 中的全部值 互不类似
  
• 0 <= amount <= 5000
  

将这题和爬楼梯作比力，发现险些千篇一律
我们将amount当作n（楼梯的阶数）;coins当作[1,2]（一次可以爬的楼梯阶数）。
以是我们可以很天然的写出以下代码：

1. def change(self, amount, coins):
2.     """
3.     :type amount: int
4.     :type coins: List[int]
5.     :rtype: int
6.     """
7.     dp=[0]*(amount+1)
8.     dp[0]=1
9.     for i in range(1,amount+1):
10.         for j in coins:
11.             if i>=j:dp[i]+=dp[i-j]  
12.     return dp[-1]

复制代码

我们将这段代码和升级后的爬楼梯的代码尴尬刁难比：

1. class Solution(object):    def climbStairs(self, n):        """        :type n: int        :type stairs: List[int]        :rtype: int        """        dp=[0]*(n+1)
2.         dp[0]=1        for i in range(1,n+1):            for j in stairs:                if i-j>=0:dp[i]+=dp[i-j]        return dp[n]

复制代码

发现：险些千篇一律
不外，我们以amount = 5, coins = [1, 2, 5]为例，输出结果应该是4
但是这个代码的输出结果为9
为什么呢？
我们来模仿一下这段代码的dp：
初始化

1. amount = 5
2. coins = [1, 2, 5]
3. dp = [0] * (amount + 1)
4. dp[0] = 1

复制代码

初始状态：

1. dp = [1, 0, 0, 0, 0, 0]

复制代码

外层循环：遍历金额

1. for i in range(1, amount + 1):

复制代码

第一轮：i = 1

1. for j in coins:
2.     if i >= j:
3.         dp[i] += dp[i - j]

复制代码

• j = 1:i >= 1(True)
  
  
  
  • dp[1] += dp[1 - 1] => dp[1] += dp[0] => dp[1] += 1 => dp[1] = 1
    
  • 组合环境：1 = 1
    
  
  

更新后的 dp：

1. dp = [1, 1, 0, 0, 0, 0]

复制代码

第二轮：i = 2

1. for j in coins:
2.     if i >= j:
3.         dp[i] += dp[i - j]

复制代码

• j = 1:i >= 1(True)
  
  
  
  • dp[2] += dp[2 - 1] => dp[2] += dp[1] => dp[2] += 1 => dp[2] = 1
    
  • 组合环境：2 = 1 + 1
    
  
  
• j = 2:i >= 2(True)
  
  
  
  • dp[2] += dp[2 - 2] => dp[2] += dp[0] => dp[2] += 1 => dp[2] = 2
    
  • 组合环境：2 = 2
    
  
  

更新后的 dp：

1. dp = [1, 1, 2, 0, 0, 0]

复制代码

第三轮：i = 3

1. for j in coins:
2.     if i >= j:
3.         dp[i] += dp[i - j]

复制代码

• j = 1:i >= 1(True)
  
  
  
  • dp[3] += dp[3 - 1] => dp[3] += dp[2] => dp[3] += 2 => dp[3] = 2
    
  • 组合环境：3 = 1 + 1 + 1, 3 = 2 + 1
    
  
  
• j = 2:i >= 2 (True)
  
  
  
  • dp[3] += dp[3 - 2] => dp[3] += dp[1] => dp[3] += 1 => dp[3] = 3
    
  • 组合环境：3 = 1 + 2
    
  
  
• j = 5: i >= 5 (False) -> 跳过
  

更新后的 dp：

1. dp = [1, 1, 2, 3, 0, 0]

复制代码

第四轮：i = 4

1. for j in coins:
2.     if i >= j:
3.         dp[i] += dp[i - j]

复制代码

• j = 1:i >= 1(True)
  
  
  
  • dp[4] += dp[4 - 1] => dp[4] += dp[3] => dp[4] += 3 => dp[4] = 3
    
  • 组合环境：4 = 1 + 1 + 1 + 1, 4 = 2 + 1 + 1, 4 = 1 + 2 + 1
    
  
  
• j = 2: i >= 2(True)
  
  
  
  • dp[4] += dp[4 - 2] => dp[4] += dp[2] => dp[4] += 2 => dp[4] = 5
    
  • 组合环境：4 = 2 + 2, 4 = 1 + 1 + 2
    
  
  
• j = 5: i >= 5 (False) -> 跳过
  

更新后的 dp：

1. dp = [1, 1, 2, 3, 5, 0]

复制代码

第五轮：i = 5

1. for j in coins:
2.     if i >= j:
3.         dp[i] += dp[i - j]

复制代码

• j = 1:``i >= 1`(True)
  
  
  
  • dp[5] += dp[5 - 1] => dp[5] += dp[4] => dp[5] += 5 => dp[5] = 5
    
  • 组合环境：5 = 1 + 1 + 1 + 1 + 1, 5 = 2 + 1 + 1 + 1, 5 = 1 + 2 + 1 + 1, 5 = 1 + 1 + 2 + 1, 5 = 1 + 1 + 1 + 2
    
  
  
• j = 2:i >= 2(True)
  
  
  
  • dp[5] += dp[5 - 2] => dp[5] += dp[3] => dp[5] += 3 => dp[5] = 8
    
  • 组合环境：5 = 2 + 2 + 1, 5 = 2 + 1 + 2, 5 = 1 + 2 + 2
    
  
  
• j = 5:i >= 5(True)
  
  
  
  • dp[5] += dp[5 - 5] => dp[5] += dp[0] => dp[5] += 1 => dp[5] = 9
    
  • 组合环境：5 = 5
    
  
  

更新后的 dp：

1. dp = [1, 1, 2, 3, 5, 9]

复制代码

终极结果

1. return dp[-1]

复制代码

返回值为 9。
具体组合环境:

• 5 = 1 + 1 + 1 + 1 + 1
  
• 5 = 2 + 1 + 1 + 1
  
• 5 = 1 + 2 + 1 + 1
  
• 5 = 1 + 1 + 2 + 1
  
• 5 = 1 + 1 + 1 + 2
  
• 5 = 2 + 2 + 1
  
• 5 = 2 + 1 + 2
  
• 5 = 1 + 2 + 2
  
• 5 = 5
  

模仿完成后，我们可以很轻松地发现标题所在：出现了很多重复的环境
而爬楼梯这一题中为什么不堕落，由于

• 5 = 1 + 2 + 1 + 1
  
• 5 = 1 + 1 + 2 + 1
  

本身在爬楼梯内里就是两种环境，而在零钱兑换Ⅱ内里确是一种环境。
为什么会如许呢？有什么办法往复掉这些重复的从而办理掉这个标题呢？
起首我们必要明白这两个概念：组合数dp和分列数dp。
5.组合数dp和分列数dp

• 组合数DP：当我们关注的是差别元素的组合而不思量次序时，应该先遍历物品（比方硬币），再遍历背包涵量（比方金额）。如许可以包管每个组合仅被盘算一次。
  
• 分列数DP：假如我们关心的是分列，即同样的元素以差别的次序出现被视为差别的结果，那么应该先遍历背包涵量，再遍历物品。如许可以确保每个元素在每个容量下都被实验放置，导致类似的元素组合大概由于放置次序差别而被多次盘算。
  

通过前面的爬楼梯与零钱兑换Ⅱ两题，想必各人都知道了两者的区别
爬楼梯是分列数dp而零钱兑换是组合数dp
那么我们怎样将我们刚刚写的零钱兑换Ⅱ中的分列数dp转换成组合数dp呢？
要想做到这一步，我们应该互换遍历的次序：先遍历硬币，再遍历金额
为什么呢？
6.为什么

要明白为什么先遍历硬币再遍历金额可以盘算组合数，而不是分列数，我们必要从动态规划（DP）的角度来分析这个标题。关键在于DP数组的更新次序和状态转移方程。
动态规划的焦点头脑

在动态规划中，我们通常用一个数组dp来存储中心结果。对于零钱兑换标题，dp表现凑足金额i的方法数。状态转移方程决定了怎样从已知的子标题结果推导出新的标题结果。
盘算组合数的准确方法

代码实现

1. def change(amount, coins):
2.     dp = [0] * (amount + 1)
3.     dp[0] = 1  # 当金额为0时，有一种方法，即不使用任何硬币
4.    
5.     # 先遍历硬币
6.     for coin in coins:
8.         # 再遍历金额
9.         for i in range(coin, amount + 1):
10.             dp[i] += dp[i - coin]
11.    
12.     return dp[amount]

复制代码

为什么先遍历硬币再遍历金额可以盘算组合数

• 初始化：
  
  1. dp = [0] * (amount + 1)
  2. dp[0] = 1  # 当金额为0时，有一种方法，即不使用任何硬币

  复制代码
• 外层循环：遍历硬币
  
  1. for coin in coins:

  复制代码
  这一步确保我们在处置惩罚每种硬币时，不会重复思量已经处置惩罚过的硬币。如许可以制止产生重复的组合。
  
• 内层循环：遍历金额
  
  1. for i in range(coin, amount + 1):
  2.     dp[i] += dp[i - coin]

  复制代码
  这一步确保我们在处置惩罚每个金额时，只会思量当前硬币对当前金额的影响。如许可以确保每个组合只被盘算一次。
  

具体表明

举例分析

假设amount = 5，coins = [1, 2, 5]，我们来渐渐模仿这个过程。

• 初始化：
  
  1. dp = [1, 0, 0, 0, 0, 0]

  复制代码
• 第一轮：coin = 1
  
  1. for i in range(1, 6):
  2.     dp[i] += dp[i - 1]

  复制代码
  
  
  • i = 1: dp[1] += dp[0] => dp[1] += 1 => dp[1] = 1
    
  • i = 2: dp[2] += dp[1] => dp[2] += 1 => dp[2] = 1
    
  • i = 3: dp[3] += dp[2] => dp[3] += 1 => dp[3] = 1
    
  • i = 4: dp[4] += dp[3] => dp[4] += 1 => dp[4] = 1
    
  • i = 5: dp[5] += dp[4] => dp[5] += 1 => dp[5] = 1
    
  1. dp = [1, 1, 1, 1, 1, 1]

  复制代码
  
  
• 第二轮：coin = 2
  
  1. for i in range(2, 6):
  2.     dp[i] += dp[i - 2]

  复制代码
  
  
  • i = 2: dp[2] += dp[0] => dp[2] += 1 => dp[2] = 2
    
  • i = 3: dp[3] += dp[1] => dp[3] += 1 => dp[3] = 2
    
  • i = 4: dp[4] += dp[2] => dp[4] += 2 => dp[4] = 3
    
  • i = 5: dp[5] += dp[3] => dp[5] += 2 => dp[5] = 3
    
  1. dp = [1, 1, 2, 2, 3, 3]

  复制代码
  
  
• 第三轮：coin = 5
  
  1. for i in range(5, 6):
  2.     dp[i] += dp[i - 5]

  复制代码
  
  
  • i = 5: dp[5] += dp[0] => dp[5] += 1 => dp[5] = 4
    
  1. dp = [1, 1, 2, 2, 3, 4]

  复制代码
  
  

终极结果

1. return dp[5]

复制代码

返回值为 4。
具体组合环境

• 5 = 1 + 1 + 1 + 1 + 1
  
• 5 = 1 + 1 + 1 + 2
  
• 5 = 1 + 2 + 2
  
• 5 = 5
  

为什么有用

• 制止重复组合：通过先遍历硬币，再遍历金额，我们确保每个组合只被盘算一次。比方，1 + 2 + 2 和 2 + 1 + 2 被视为同一个组合，由于我们在处置惩罚硬币1时已经思量了全部大概的组合方式。
  
• 状态转移方程：dp += dp[i - coin] 只思量当前硬币对当前金额的影响，确保每个组合只被盘算一次。
  

通过这种方式，我们可以有用土地算出组合数，而不是分列数。
以是零钱兑换Ⅱ这一题我们就可以办理了：

1. class Solution(object):
2.     def change(self, amount, coins):
3.         """
4.         :type amount: int
5.         :type coins: List[int]
6.         :rtype: int
7.         """
8.         dp=[0]*(amount+1)
9.         dp[0]=1
10.         for j in coins:
11.             for i in range(1,amount+1):
12.                 if i>=j:dp[i]+=dp[i-j]
13.         return dp[-1]

复制代码

思索三：你是否在零钱兑换Ⅱ中看到背包标题的影子？
7.背包标题

01背包标题

界说

01背包标题是一种经典的动态规划标题，此中有一组物品，每个物品有一个重量和一个代价。我们必要选择一些物品放入一个容量有限的背包中，使得背包中物品的总代价最大，同时总重量不高出背包的容量。每个物品只能选择0个或1个，不能重复选择。
完全背包标题

界说

完全背包标题与01背包标题类似，但每个物品可以被选择无穷次。也就是说，每个物品可以选择0个、1个、2个、…，直到总重量高出背包涵量为止。
示例

假设我们有以下物品和一个容量为10的背包：
物品重量代价A23B34C45D58我们的目标是选择一些物品放入背包中，使得总代价最大，同时总重量不高出10。
我们先来看完全背包：这是不是和零钱兑换Ⅱ非常相似？
我们可以把物品重量w=[2,3,4,5]当作coins，将容量c当作amount
只不外是问的标题差别而已
一个是求最大代价，一个是求凑成总金额的硬币组合数
这题我们界说dp表现当背包涵量为i时所装物品的最大代价，
而dp是怎么来的呢？
在这个示例中，当i>=5时，我们有四种选择：

• 在dp[i-2]时再装一个代价为3的物品A
  
• 在dp[i-3]时再装一个代价为4的物品B
  
• 在dp[i-4]时再装一个代价为5的物品C
  
• 在dp[i-5]时再装一个代价为8的物品D
  

以是有：
dp=max(dp,dp[i-某个物品的重量]+该物品的代价)
以是参考零钱兑换，我们可以很容易地写出代码：

1. w=[2,3,4,5]
2. v=[3,4,5,8]
3. c=10
4. dp=[0]*(c+1)
5. for i in range(1,c+1):
6.     for j in range(len(w)):
7.         if i-w[j]>=0:dp[i]=max(dp[i],dp[i-w[j]]+v[j])
8. print(dp)
9. # 输出： [0, 0, 3, 4, 6, 8, 9, 11, 12, 14, 16]

复制代码

这种写法是分列数dp，但这题显着是组合数dp，那为什么写成分列数dp也是准确的呢？
由于完全背包标题本身答应每个物品被选择无穷次。这意味着无论我们先遍历物品照旧先遍历容量，每个物品在每个容量下的最优解都会被多次思量，从而不会产生重复计数的标题。
但01背包就不一样了，我们必须老诚实实写成组合数dp，由于01背包每个物品只能选择一次。
为了确保每个物品只能选择一次，我们还得倒序遍历dp数组：

1. w=[2,3,4,5]
2. v=[3,4,5,8]
3. c=10
4. dp=[0]*(c+1)
5. for j in range(len(w)):
6.     for i in range(c,0,-1):
7.         if i-w[j]>=0:dp[i]=max(dp[i],dp[i-w[j]]+v[j])
8. print(dp)
9. # 输出： [0, 0, 3, 4, 5, 8, 8, 11, 12, 13, 15]

复制代码

那么为什么要倒序遍历dp数组呢？
为什么必要倒序遍历

• 制止重复利用同一个物品：
  
  
  
  • 假如正序遍历数组（从 weight 到 capacity），在更新 dp[j] 时，大概会利用已经更新过的 dp[j - weight]，导致同一个物品被多次利用。
    
  • 比方，假设我们有一个物品A（重量2，代价6），背包涵量为4，dp 数组初始化为 [0, 0, 0, 0, 0]。
    
  
  
• 正序遍历的标题：
  
  
  
  • 正序遍历时，dp数组的更新次序如下：
    
    
    
    • dp[2] = max(dp[2], dp[0] + 6) = 6
      
    • dp[3] = max(dp[3], dp[1] + 6) = 6
      
    • dp[4] = max(dp[4], dp[2] + 6) = 12
      
    
    
  • 这里，dp[4] 的值是12，但现实上我们只能选择一次物品A，以是准确的值应该是6。
    
  
  
• 倒序遍历的优点：
  
  
  
  • 倒序遍历时，dp数组的更新次序如下：
    
    
    
    • dp[4] = max(dp[4], dp[2] + 6) = 6
      
    • dp[3] = max(dp[3], dp[1] + 6) = 6
      
    • dp[2] = max(dp[2], dp[0] + 6) = 6
      
    
    
  • 这里，dp[4] 的值是6，准确地反映了我们只能选择一次物品A。
    
  
  

8.结语

​ 这篇文章告急讲动态规划算法，我们从斐波那契数列讲起，通过力扣中的爬楼梯、零钱兑换、零钱兑换Ⅱ这几道经典动态规划题，讲了动态规划的根本方法、以及组合数dp与分列数dp，并通过它们引出了动态规划中的背包标题。我们联合前面的示例，写出了完全背包和01背包的代码，并表明白其内部的原理 。这里增补一点，背包标题写代码的次序应该是先写二维，再压缩成一维，这是背包标题正常的解法及思绪。本篇文章提供了明白背包标题的另一个思绪，假如各人明白不了背包标题的正常思绪，可以参考一下本人的思绪，如有一些必要指正的地方，欢迎各人指正！