数据结构：动态规划基础

OutlierLi

已于 2024-09-22 19:17:34 修改

阅读量1.4k

点赞数 12

分类专栏：数据结构代码随想录文章标签：数据结构动态规划算法

于 2024-09-22 17:13:02 首次发布

本文链接：https://blog.csdn.net/Input_print/article/details/142439885

版权

数据结构同时被 2 个专栏收录

14 篇文章

订阅专栏

代码随想录

9 篇文章

订阅专栏

数据结构：动态规划基础

(代码随想录学习笔记代码随想录)

基础概念

什么是动态规划？

动态规划，简称DP，如果某一个问题有很多重叠子问题，并且子问题和子问题之间有依赖关系，使用动态规划是最有效的；

贪心和动态规划的区别

同样是一个问题可以分为多个子问题，不同的是：

贪心算法中，子问题之间可以没有强关联，即在取钞票问题中，拿最大面值钞票这一策略在任何局部都是一样的；并且每个局部都可以找到一个最优解，该最优解和上一个局部如何选择没有关系，即上一个局部即使没有选择局部最优，本局部的局部最优解法没有改变；
动态规划中，子问题之间有强关联，即一个子问题的解法要依靠前面的子问题选择的解法，每一个状态一定是由之前的状态推导出来的；在此类问题中，我们未必可以确定局部最优，只能不断从一个状态转移到另一个状态，然后推导出全局解，选择最优的全局解，即只有全局最优；

贪心是从局部最优推导出全局最优；动态规划是从局部推导出全局；

所以贪心能解决的问题，一般动态规划都能解决，但是选择贪心可能更高效一点；贪心解决不了的问题（即局部最优推不出全局最优），动态规划也可以解决；

背包问题的例子：

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

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

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。所以贪心解决不了动态规划的问题。

动态规划是由前一个状态推导出来的，而贪心算法是局部直接选最优；

解题步骤

动态规划五部曲：

确定dp数组以及下标的含义；
确定递推公式；
dp数组如何初始化；
确定遍历顺序；
举例推导dp数组；（即debug，看dp数组运行过程是否和我们推导的一样）

背包理论

416.分割等和子集1

背包问题：背包容量有限，要让背包中装的物品的价值总量最大；

01背包

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

暴力解法：每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是 $O(2^n)$ ，这里的n表示物品数量。

动态规划五部曲：

确定dp数组及其含义：二维dp[][]数组，其中dp[i][j]代表从下标为[0~i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
递推公式：看有几条途径可以到达dp[i][j]；
- 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当加入物品i之后背包重量大于背包容量j时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
- 放物品i：
  - 要放入物品i，则放入之前背包容量应该为j - weight[i]；所以由dp[i - 1][j - weight[i]]推出；
  - dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值；
  - dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值；
- 递归公式：取不放物品i的最大值和放物品i的最大值中的最大值，即dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])；
初始化dp[][]数组：对于二维数组，一般初始化一行和一列，即初始化dp[0][j]和dp[i][0]；
- 初始化dp[i][0]：背包容量为0，所以全部初始化为0；
- 初始化dp[0][j]：对于j < weight[0]的部分，初始化为0，对于j >= weight[0]的部分，初始化为weight[0]，即只选择0号物品装入；
- 其余位置初始化为0，最后都会被覆盖；
确定遍历顺序：从左上角开始，向右下角遍历；有两个遍历的维度：物品和背包重量；
- 先遍历物品，后遍历背包重量；
- 先遍历背包重量，后遍历物品；
- 无论先遍历哪一个都可以，因为都是从左上角到右下角，只要左边和上边的元素都先求出来就可以，但是先遍历物品更好，因为更好理解；
模拟dp数组执行过程；

// 初始化
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

滚动数组实现01背包

之前实现的01背包中，使用了二维数组dp[][]，空间效率差，其实可以用滚动数组实现，让二维数组dp[][]变成一维数组dp[]，可以提高空间效率；

将二维数组转换为一维滚动数组，关键在于状态的压缩；压缩过程如下：

二维数组递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])；
如果将dp[i - 1]那一层拷贝到dp[i]这一层上，则状态转移方程变为：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]；
- 什么意思？为什么能将之前的一层拷贝到现在的一层上？
- 在确定dp[i][j]时，本行左边的dp[i][0 ~ j-1]内的结果其实还没开始确认（都是初始化时时的值，大部分都是0），而dp[i][j]右边的虽然确认了，但是dp[i - 1][j]右边的和dp[i][j]没有关系；
- 既然dp[i - 1][j]左边的用于推导dp[i][j]，而dp[i][j]左边的又还没有开始确认，那么将dp[i - 1][j]左边的覆盖到dp[i][j]左边没有任何问题；
既然可以拷贝到一层上，就没必要用二维数组了，直接使用一维数组，之前二维数组向下遍历一层，现在一维数组直接覆盖一层；
之前dp[i][j]的含义：i代表物品，j代表背包容量；
此时dp[i]的含义：i代表背包容量，假设当前遍历轮次为第k轮，则从[0~k]中选取物品加入容量为j的背包中；（如此一来中间状态在最后没办法保存，即如果找到结果后，突然减小j，我们又要重新运行一遍代码）
改进后的递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])；就是将之前i - 1的部分全部去掉，而i和j的部分不变；

滚动数组实现的01背包，动态规划五部曲：

dp[j]代表容量为j的背包最大可以放多少价值的货物；
状态转移方程：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])；
初始化dp[j]数组，如果物品价值均大于等于0，则数组全部初始化为0；
遍历顺序（尤其注意，从二维数组看）：从右向左遍历；（因为数组是滚动的，dp[j]左边的是上一轮的结果，并且上一轮结果才能推出dp[j]，所以左边的不能被本轮结果覆盖，所以遍历从右向左，从后往前）
- 之前二维数组先背包容量或者先物品都可以，但是换成滚动数组不行；（所以之前说先物品好，因为可以方便地改为滚动数组）
- 只能先遍历物品，后遍历背包容量；即外层循环递增i，内层循环递减j；
模拟dp[]的过程；

vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;

// 初始化
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

状态转移方程

求最大值：当我们需要求最大值时，通常使用max函数来比较当前状态和新状态之间的大小，并选择较大的值作为新的状态。例如：dp[i] = max(dp[i], dp[i-w] + v)，表示比较当前状态dp[i]和选择当前物品后的新状态dp[i-w] + v，将较大的值赋给dp[i]。
累加：在一些问题中，我们需要将多个状态值累加起来。例如：dp[i] = dp[i-1] + dp[i-2]，表示将前两个状态的值相加，并将结果赋给当前状态。
1. 尤其是对于最多方法数之类的问题，一般要累加；
加上nums[i]：在01背包中，有时候dp[i][j]由dp[i - 1][j]和dp[i - 1][j - weight[i]] + nums[i]共同推出；
1. 如果dp[i][j]代表最大物品价值，则要加；
不加nums[i]：在01背包中，有时候dp[i][j]由dp[i - 1][j]和dp[i - 1][j - weight[i]]共同推出，不用加nums[i]；
1. 如果dp[i][j]代表方法数量，选择了i物品，也不应该加上价值，而是相当于dp[i - 1][j - weight[i]] * 1，即选择了i物品，只代表一种方法；

状态转移方程多种多样，一定要根据实际问题处理，而不是单纯套公式；尤其是分清楚dp[i][j]代表的含义和性质，是方法数还是价值总量，是求最大值还是累加；

常见的情况：

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])；
- 初始化应该初始化一个最大值（除了dp[0]），以便于状态转移时可以覆盖初始值；
问装满背包有几种方法：dp[j] += dp[j - nums[i]]；
- dp[0] = 1，初始化虽然没有意义，但是有用；
问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])；（和第一个本质一样）
- 初始化应该初始化一个最小值（除了dp[0]），以便于状态转移时可以覆盖初始值；
问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j])；
- 初始化应该初始化一个最大值（除了dp[0]），以便于状态转移时可以覆盖初始值；

完全背包

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

例如：

物品	重量	价值
0	1	15
1	3	20
2	4	30

当背包最大重量为4时，选择4件物品0放入背包，总价值为60，此时总价值最大；

01背包和完全背包唯一不同就是体现在遍历顺序上；

代码对比：

// 01背包（物品只能被添加一次）
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量（从后往前）
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

// 完全背包（物品可以被添加多次）
// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量（从小到大）
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

为什么遍历物品在外层循环，遍历背包容量在内层循环？在01背包中，如果使用滚动数组优化，则一定要先物品后背包容量，但是在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！

01背包问题中，我们需要在每个背包容量下决定是否选择当前物品放入背包。为了保证在计算dp[j]时，我们使用的是上一行或上一轮计算出来的dp[j-w]，即在选择当前物品时，我们需要使用的是上一行或上一轮计算出来的dp[j-w]。因此，在01背包问题中，我们需要先遍历物品，然后再遍历背包容量，以确保在计算dp[j]时，我们使用的是正确的上一行或上一轮的dp[j-w]。

完全背包问题中，我们需要在每个背包容量下决定是否选择当前物品放入背包。不同于01背包问题，完全背包问题允许我们选择多次使用同一个物品。因此，我们不再需要考虑上一行或上一轮计算出来的dp[j - w]。在完全背包问题中，我们只需要确保在计算dp[j]时，我们使用的是当前行或当前轮计算出来的dp[j - w]即可。

所以，在完全背包问题中，对于一维dp数组来说，两个嵌套的循环的顺序是无所谓的，因为我们不再依赖上一行或上一轮的计算结果。我们只需要确保在计算dp[j]时，我们使用的是当前行或当前轮计算出来的dp[j - w]即可（虽然循环顺序无所谓，但是背包容量必须从小到大而不是01背包的从大到小）。

动态规划-完全背包2

dp[1][4]：在物品0和物品1中选择，并且可以重复选择，找到重量小于4的最大价值；

dp[1][4] = max(dp[0][4], dp[1][4 - 3] + 20) = 45；其中3代表物品1的重量，20代表物品1的价值；

但是如果不是问最大价值，而是问装满背包的方法数量，则要考虑内外层循环的顺序；所以最好还是和01背包内外层循环顺序保持一致；

背包问题遍历顺序总结

01背包：背包容量必须从大到小遍历，从target到nums[i]；
- 二维数组：内外层遍历顺序无所谓；
- 滚动数组：只能先遍历物品再遍历背包容量；
完全背包：背包容量必须从小到大遍历，从nums[i]或0到target；
- 组合：外层for循环遍历物品，内层for遍历背包；
- 排列：外层for遍历背包，内层for循环遍历物品；

对于背包问题，其实递推公式算是容易的，难是难在遍历顺序上，如果把遍历顺序搞透，才算是真正理解了。

多重背包

有 $N$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品最多有 $M_i$ 件可用，每件耗费的空间是 $C_i$ ，价值是 $W_i$ 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

01背包是每个物品只能使用1次，完全背包是每个物品能够使用无限次，多重背包是每个物品都规定了使用次数；

如果将第 $i$ 种物品最多有 $M_i$ 件可用摊开，即把每一种物品都展开为 $M_i$ 个物品；这样每个物品都只能只用1次，就变成了01背包；

例如：

物品	重量	价值	数量
0	1	15	1
1	3	20	1
2	4	30	2

展开为01背包问题

物品	重量	价值
0	1	15
1	3	20
2	4	30
2	4	30

转换为01背包之后使用动态规划：

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int bagWeight,n;
    cin >> bagWeight >> n;
    vector<int> weight(n, 0);
    vector<int> value(n, 0);
    vector<int> nums(n, 0);
    for (int i = 0; i < n; i++) cin >> weight[i];
    for (int i = 0; i < n; i++) cin >> value[i];
    for (int i = 0; i < n; i++) cin >> nums[i];
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < n; i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            // 以上为01背包，然后加一个遍历个数
            for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数
                dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
        }
    }
    cout << dp[bagWeight] << endl;
}

多重背包转换01背包问题就是把每种物品的数量，打包成一个个独立的包。多重背包在面试中基本不会出现，力扣上也没有对应的题目，大家对多重背包的掌握程度知道它是一种01背包，并能在01背包的基础上写出对应代码就可以了。

数据结构：动态规划基础

数据结构：动态规划基础

基础概念

什么是动态规划？

贪心和动态规划的区别

背包问题的例子：

解题步骤

背包理论

01背包

滚动数组实现01背包

状态转移方程

完全背包

背包问题遍历顺序总结

多重背包

例题

斐波那契数列

爬楼梯

使用最小花费爬楼梯

不同路径

不同路径II

整数拆分

不同的二叉搜索树

分割等和子集

最后一块石头的重量II

目标和

一和零

零钱兑换II

组合总数IV

爬楼梯（进阶版）

零钱兑换

完全平方数

单词拆分

总结