文章目录
- 关于01背包中一维dp和二维dp的比较
- 二维dp代码
- 一维dp代码
- 【模板】01背包
- 分割等和子集
- 目标和
- 最后一块石头重量||
- 完全背包问题的解决方法
- 【模板】完全背包
- 零钱兑换
- 零钱兑换||
- 完全平方数
关于01背包中一维dp和二维dp的比较
-
二维dp
在 0/1 背包问题 中，二维DP的状态转移是 dp[i][j]，表示前 i 个物品中，是否能够装入容量为 j 的背包。 -
一维dp
在 0/1 背包问题 中，通常会优化为一维DP，使用一维数组 dp[j] 来表示当前背包容量为 j 时的最大价值。通过从右到左更新，避免了重复使用相同的物品。
在空间复杂度上：
- 空间复杂度：
二维DP：通常是 O(n * m)，其中 n 和 m 是问题的两个维度。空间较大，尤其是在问题的规模增大时。
一维DP：通常是 O(m)，通过滚动数组优化，只需要存储当前状态所需要的部分，显著降低空间复杂度。 - 时间复杂度：
二维DP：与二维状态转移相关，因此时间复杂度通常是 O(n * m)，这里 n 和 m 是问题的两个维度。
一维DP：时间复杂度通常与二维DP相同，但因为我们只使用一维数组，它通常能通过节省空间来获得更好的性能，尤其在状态可以滚动的情况下。 - 实现难度：
二维DP：一般来说，二维DP的实现更加直观，直接反映了问题的结构。它适用于有多个独立维度需要考虑的问题。
一维DP：实现相对复杂，特别是在需要滚动数组的情况下，需要通过巧妙的设计和状态转移来避免重复计算，但空间复杂度的优化是其主要优点。 - 代码可读性：
二维DP：代码通常比较清晰，因为每个维度的状态都是明确的，比较容易理解。
一维DP：通过“滚动”数组的优化，代码可能不如二维DP直观，特别是当涉及到倒序更新状态时。
二维dp代码
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++)
{for (int w = 0; w <= W; w++) {dp[i][w] = dp[i-1][w]; // 不选当前物品if (w >= weights[i-1]) {dp[i][w] = max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1]);}}
}
return dp[n][W];
二维DP 中，我们需要一个 n+1 行，W+1 列的数组，dp[i][w] 表示前 i 个物品能够填充容量为 w 的背包。
一维dp代码
vector<int> dp(W + 1, 0);
for (int i = 1; i <= n; i++)
{// 从大到小遍历，防止重复更新for (int w = W; w >= weights[i-1]; w--) {dp[w] = max(dp[w], dp[w - weights[i-1]] + values[i-1]);}
}
return dp[W];
一维DP 中，我们只需要一个大小为 W+1 的数组 dp，它保存的是当前容量下的最大价值。通过倒序遍历 w，我们确保每个物品只更新一次，避免覆盖之前的状态。
【模板】01背包
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;const int N = 1010; // 定义常量N，表示物品和容量的最大值
int n, v; // n: 物品的数量, v: 背包的容量
int dp[N][N]; // dp数组，二维数组，其中dp[i][j]表示前i个物品放入容量为j的背包中所得到的最大价值
int V[N], w[N]; // V数组存储每个物品的体积，w数组存储每个物品的价值int main()
{cin >> n >> v; // 输入物品数量n和背包容量vfor(int i = 1; i <= n; i++){cin >> V[i] >> w[i]; // 输入每个物品的体积V[i]和价值w[i]}// 0/1背包的动态规划过程// i表示物品的编号，j表示背包容量for(int i = 1; i <= n; i++) // 遍历每个物品{for(int j = 1; j <= v; j++) // 遍历每个背包容量{dp[i][j] = dp[i - 1][j]; // 不选当前物品，最大价值为前i-1个物品在容量j下的最大价值if(j - V[i] >= 0) // 如果背包容量j足够放下当前物品dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - V[i]] + w[i]); // 选择当前物品或不选择当前物品}}cout << dp[n][v] << endl; // 输出使用动态规划后的最大价值// 重置dp数组，并进行第二次动态规划memset(dp, 0, sizeof(dp)); // 重置dp数组，初始化为0for(int j = 1; j <= v; j++) dp[0][j] = -1; // dp[0][j]表示选择第0个物品时背包容量为j时的最大价值，初始化为-1，表示不可能的状态// 第二次背包问题的动态规划计算for(int i = 1; i <= n; i++) // 遍历每个物品{for(int j = 1; j <= v; j++) // 遍历每个背包容量{dp[i][j] = dp[i - 1][j]; // 不选当前物品if(j >= V[i] && dp[i - 1][j - V[i]] != -1) // 判断当前背包容量是否足够，且前一个状态有效dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - V[i]] + w[i]); // 选择当前物品或不选择}}// 输出第二次动态规划后的最大价值，如果dp[n][v]为-1，说明无法填充背包，输出0，否则输出最大价值cout << (dp[n][v] == -1 ? 0 : dp[n][v]) << endl;return 0;
}
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;const int N = 1010; // 定义一个常量N表示物品数量的最大值（最大背包容量为v）
int n, v; // n为物品数量，v为背包容量
int dp[N]; // dp数组，用来存储每个容量下能够获得的最大价值
int V[N], w[N]; // V数组存储每个物品的体积，w数组存储每个物品的价值int main()
{cin >> n >> v; // 输入物品的数量n和背包的容量vfor(int i = 1; i <= n; i++){cin >> V[i] >> w[i]; // 输入每个物品的体积V[i]和价值w[i]}// 0/1背包动态规划// i表示是否选择物品i，j表示当前背包容量剩余空间for(int i = 1; i <= n; i++) // 遍历每个物品{for(int j = v; j >= V[i]; j--) // 遍历容量从v到V[i]（逆序保证每个物品只能选择一次）{dp[j] = max(dp[j], dp[j - V[i]] + w[i]); // 选择当前物品，更新dp[j]}}cout << dp[v] << endl; // 输出使用0/1背包的最大价值memset(dp, 0, sizeof(dp)); // 重置dp数组for(int j = 1; j <= v; j++) dp[j] = -1; // 初始化dp数组，-1表示无法达到该容量for(int i = 1; i <= n; i++) // 遍历每个物品{for(int j = v; j >= V[i]; j--) // 遍历容量从v到V[i]（逆序保证每个物品只能选择一次）{if(dp[j - V[i]] != -1) // 判断前一个状态是否有效dp[j] = max(dp[j], dp[j - V[i]] + w[i]); // 如果有效，更新dp[j]}}cout << (dp[v] == -1 ? 0 : dp[v]) << endl; // 输出使用另一种方式计算的最大价值return 0;
}
分割等和子集
class Solution
{
public:bool canPartition(vector<int>& nums) {int n = nums.size(); // 数组的长度int sum = accumulate(nums.begin(), nums.end(), 0); // 计算数组元素的总和// 如果总和是奇数，无法平分为两个相等的子集if(sum % 2 == 1) return false;// 目标是找到和为 sum / 2 的子集vector<vector<bool>> dp(n + 1, vector<bool>(sum / 2 + 1)); // dp[i][j] 表示是否可以通过前 i 个元素，得到和为 j 的子集// 初始化：当目标和为 0 时，任何前 i 个元素都可以通过不选择元素得到和为 0for(int i = 0; i <= n; i++) dp[i][0] = true;// 遍历每一个元素，更新 dp 数组for(int i = 1; i <= n; i++){for(int j = 1; j <= sum / 2; j++){dp[i][j] = dp[i - 1][j]; // 不选当前元素，dp[i][j]继承自上一个元素的状态if(j >= nums[i - 1]) // 如果当前目标和 j 大于或等于当前元素 nums[i - 1]dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]]; // 可以选择当前元素，或者不选}}// 最终结果：是否存在和为 sum / 2 的子集return dp[n][sum / 2];}
};
class Solution
{
public:bool canPartition(vector<int>& nums) {int n = nums.size(); // 数组的长度int sum = accumulate(nums.begin(), nums.end(), 0); // 计算数组元素的总和// 如果总和是奇数，无法平分为两个相等的子集if(sum % 2 == 1) return false;// 目标是找到和为 sum / 2 的子集vector<bool> dp(sum / 2 + 1); // dp[i] 表示是否存在和为 i 的子集dp[0] = true; // 和为 0 的子集一定存在（即不选择任何元素）// 遍历数组的每一个元素for(int i = 1; i <= n; i++){// 从后往前更新 dp 数组，确保每个元素只使用一次for(int j = sum / 2; j >= nums[i - 1]; j--){dp[j] = dp[j] || dp[j - nums[i - 1]]; // 如果可以达到 dp[j - nums[i - 1]]，则 dp[j] 也可以达到}}// 最后判断是否存在和为 sum / 2 的子集return dp[sum / 2];}
};
目标和
class Solution
{
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = accumulate(nums.begin(), nums.end(), 0); // 计算数组的总和int n = nums.size(); // 数组的长度int aim = (sum + target) / 2; // 目标和 P，要求 P = (sum + target) / 2// 如果目标和小于 0 或者 (sum + target) 不是偶数，返回 0if(aim < 0 || (sum + target) % 2) return 0;// dp[i][j] 表示在前 i 个元素中，是否存在一个子集，和为 jvector<vector<int>> dp(n + 1, vector<int>(aim + 1, 0)); // 初始化动态规划数组dp[0][0] = 1; // 和为 0 时，选取 0 个元素的方式只有 1 种，即不选任何元素// 遍历每个元素for(int i = 1; i <= n; i++){// 遍历所有可能的子集和 jfor(int j = 0; j <= aim; j++){dp[i][j] = dp[i - 1][j]; // 不选择当前元素，继承上一个状态// 如果当前目标和 j 大于等于当前元素 nums[i - 1]，可以选择当前元素if(j >= nums[i - 1]){dp[i][j] += dp[i - 1][j - nums[i - 1]]; // 选择当前元素时，更新 dp 状态}}}// 最终结果：dp[n][aim] 表示是否能选出和为 aim 的子集return dp[n][aim];}
};
class Solution
{
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = accumulate(nums.begin(), nums.end(), 0); // 计算数组的总和int n = nums.size(); // 数组的长度int aim = (sum + target) / 2; // 目标和 P，要求 P = (sum + target) / 2// 如果目标和小于 0 或者 (sum + target) 不是偶数，返回 0if(aim < 0 || (sum + target) % 2) return 0;// dp[j] 表示是否能选出和为 j 的子集vector<int> dp(aim + 1, 0); // 初始化一维动态规划数组dp[0] = 1; // 和为 0 时，选取 0 个元素的方式只有 1 种，即不选任何元素// 遍历每个元素for(int i = 1; i <= n; i++){// 从后往前更新 dp 数组，确保每个元素只用一次for(int j = aim; j >= nums[i - 1]; j--){dp[j] = dp[j] + dp[j - nums[i - 1]]; // 更新 dp[j]，增加当前元素的选择}}// 最终结果：dp[aim] 表示能否选出和为 aim 的子集return dp[aim];}
};
最后一块石头重量||
class Solution
{
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size(); // 获取石头的数量int sum = accumulate(stones.begin(), stones.end(), 0); // 计算所有石头的总和int aim = sum / 2; // 目标是找到一个和尽量接近 sum / 2 的子集// dp[i][j] 表示前 i 块石头中，是否能组成和为 j 的子集vector<vector<int>> dp(n + 1, vector<int>(aim + 1, 0)); // 初始化动态规划数组// 遍历每一块石头for(int i = 1; i <= n; i++){// 遍历可能的和 jfor(int j = 0; j <= aim; j++){dp[i][j] = dp[i - 1][j]; // 不选择当前石头，继承上一个状态// 如果当前和 j 大于等于当前石头的重量 stones[i - 1]，选择当前石头if(j >= stones[i - 1])dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);}}// 最终结果：最小的差值为 sum - 2 * dp[n][aim]return sum - 2 * dp[n][aim];}
};
class Solution
{
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size(); // 获取石头的数量int sum = accumulate(stones.begin(), stones.end(), 0); // 计算所有石头的总和int aim = sum / 2; // 目标是找到一个和尽量接近 sum / 2 的子集// dp[j] 表示是否能选出和为 j 的子集vector<int> dp(aim + 1, 0); // 初始化一维动态规划数组dp[0] = 1; // 和为 0 时，选取 0 个元素的方式只有 1 种，即不选任何元素// 遍历每一块石头for(int i = 1; i <= n; i++){// 从后往前更新 dp 数组，确保每个元素只用一次for(int j = aim; j >= stones[i - 1]; j--){dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]); // 更新 dp[j]，增加当前石头的选择}}// 最终结果：最小的差值为 sum - 2 * dp[aim]return sum - 2 * dp[aim];}
};
完全背包问题的解决方法
问题： 给定多种物品，每种物品可以无限次地选择，背包的容量为V，求如何选择物品使得总价值最大，同时不超过背包容量。
解法思路： 完全背包问题允许每个物品被选多次，因此需要用动态规划来解决。我们可以使用一维数组来优化空间复杂度。
解法步骤：
- 初始化： 创建一个一维数组dp，大小为背包容量V+1，初始化所有元素为0，表示在容量0时的价值为0，其余容量初始化为0，后续处理中会被更新。
- 遍历物品： 对于每个物品，体积为v[i]，价值为w[i]。从背包容量V开始倒序遍历到物品体积v[i]。
- 更新状态： 对于每个容量j，检查是否可以放入当前物品（即j >= v[i]），如果可以，则更新dp[j]为dp[j - v[i]] + w[i]，即选择当前物品后的最大价值。
- 返回结果： 最终，dp[V]将存储背包容量为V时的最大价值。
- 下面给出一个模板题，第二部分可以记忆将问题转化之后，直接套模板
【模板】完全背包
重点看第二部分，完全背包问题
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;const int N = 1010; // 定义常量N，表示物品数量的最大值
int n, V; // n表示物品的数量，V表示背包的容量
int v[N], w[N]; // v数组存储每个物品的体积，w数组存储每个物品的价值
int dp[N][N]; // dp二维数组，用来保存状态，dp[i][j]表示前i个物品，在容量为j时的最大价值int main()
{cin >> n >> V; // 输入物品数量n和背包的容量Vfor(int i = 1; i <= n; i++) // 输入每个物品的体积和价值{cin >> v[i] >> w[i]; // 输入物品i的体积v[i]和价值w[i]}// 第一部分：0-1背包的标准动态规划解法for(int i = 1; i <= n; i++) // 遍历每个物品{for(int j = 0; j <= V; j++) // 遍历每个容量{dp[i][j] = dp[i - 1][j]; // 不选第i个物品时，最大价值等于前i-1个物品在当前容量下的最大价值if(j >= v[i]) // 如果当前容量足够容纳第i个物品dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]); // 比较选和不选第i个物品后的最大价值}}// 输出第一次背包问题的结果，dp[n][V]即为前n个物品，容量V时的最大价值cout << dp[n][V] << endl;// 第二部分：带有限制条件的背包问题（物品是否能被选中的限制）————完全背包问题memset(dp, 0, sizeof(dp)); // 重置dp数组for(int j = 1; j <= V; j++) dp[0][j] = -1; // 初始化dp[0][j]，表示没有物品时，容量j不可能选择任何物品，初始化为-1for(int i = 1; i <= n; i++) // 遍历每个物品{for(int j = 0; j <= V; j++) // 遍历每个容量{dp[i][j] = dp[i - 1][j]; // 不选第i个物品时，最大价值等于前i-1个物品在当前容量下的最大价值if(j >= v[i] && dp[i][j - v[i]] != -1) // 如果当前容量足够容纳第i个物品并且dp[i][j - v[i]]不为-1，表示可以选择第i个物品dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]); // 比较选和不选第i个物品后的最大价值}}// 输出第二部分背包问题的结果，若dp[n][V]为-1，表示无法选择任何物品，则输出0cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
}
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;const int N = 1010; // 定义常量N，表示物品数量的最大值
int n, V; // n表示物品数量，V表示背包的容量
int v[N], w[N]; // v数组存储每个物品的体积，w数组存储每个物品的价值
int dp[N][N]; // dp二维数组，用来保存状态，dp[i][j]表示前i个物品，在容量为j时的最大价值int main()
{cin >> n >> V; // 输入物品数量n和背包的容量Vfor(int i = 1; i <= n; i++) // 输入每个物品的体积和价值{cin >> v[i] >> w[i]; // 输入物品i的体积v[i]和价值w[i]}// 第一部分：标准0-1背包的动态规划解法for(int i = 1; i <= n; i++) // 遍历每个物品{for(int j = 0; j <= V; j++) // 遍历每个容量{dp[i][j] = dp[i - 1][j]; // 不选第i个物品时，最大价值等于前i-1个物品在当前容量下的最大价值if(j >= v[i]) // 如果当前容量足够容纳第i个物品dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]); // 比较选和不选第i个物品后的最大价值}}// 输出第一次背包问题的结果，dp[n][V]即为前n个物品，容量V时的最大价值cout << dp[n][V] << endl;// 第二部分：带有限制条件的背包问题（物品是否能被选中的限制）memset(dp, 0, sizeof(dp)); // 重置dp数组for(int j = 1; j <= V; j++) dp[0][j] = -1; // 初始化dp[0][j]，表示没有物品时，容量j不可能选择任何物品，初始化为-1for(int i = 1; i <= n; i++) // 遍历每个物品{for(int j = 0; j <= V; j++) // 遍历每个容量{dp[i][j] = dp[i - 1][j]; // 不选第i个物品时，最大价值等于前i-1个物品在当前容量下的最大价值if(j >= v[i] && dp[i][j - v[i]] != -1) // 如果当前容量足够容纳第i个物品并且dp[i][j - v[i]]不为-1，表示可以选择第i个物品dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]); // 比较选和不选第i个物品后的最大价值}}// 输出第二部分背包问题的结果，若dp[n][V]为-1，表示无法选择任何物品，则输出0cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
}
零钱兑换
class Solution
{
public:int coinChange(vector<int>& coins, int amount) {int n = coins.size(); // 获取硬币种类的数量// 创建二维dp数组，dp[i][j]表示使用前i种硬币组成金额j的最小硬币数vector<vector<int>> dp(n + 1, vector<int>(amount + 1));// 初始化第一行，即没有任何硬币时，不可能组成任何金额（除了金额为0时为0）for(int j = 1; j <= amount; j++) dp[0][j] = 0x3f3f3f3f; // 0x3f3f3f3f是一个很大的数，表示无法达成目标金额// 填充dp表for(int i = 1; i <= n; i++) // 遍历每种硬币{for(int j = 0; j <= amount; j++) // 遍历每个金额{// 先不使用当前硬币，继承前一种硬币的结果dp[i][j] = dp[i - 1][j];// 如果当前金额j大于等于当前硬币的面额，则可以考虑使用当前硬币if(j >= coins[i - 1])dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1); // 更新dp[i][j]为使用当前硬币后的最小硬币数}}// 如果最后的结果还是很大的数，表示无法组成目标金额，返回-1return dp[n][amount] >= 0x3f3f3f3f ? -1 : dp[n][amount];}
};
class Solution
{
public:int coinChange(vector<int>& coins, int amount) {int n = coins.size(); // 获取硬币种类的数量// 创建一维dp数组，dp[j]表示组成金额j的最小硬币数，初始化为一个非常大的数，表示不能用硬币组合的金额vector<int> dp(amount + 1, 0x3f3f3f3f);dp[0] = 0; // 用0个硬币组成金额0所需的硬币数为0// 遍历每一种硬币for(int i = 1; i <= n; i++){// 对于每个硬币，尝试更新dp数组for(int j = coins[i - 1]; j <= amount; j++) // 从当前硬币的面额开始更新dp数组{// 如果可以用当前硬币（面额为coins[i-1]）更新dp[j]，则更新dp[j]为最小的硬币数dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);}}// 最后判断dp[amount]的值，如果它仍然是初始化的大数，表示不能用硬币组合成该金额，返回-1；否则返回最小硬币数return dp[amount] >= 0x3f3f3f3f ? -1 : dp[amount];}
};
零钱兑换||
class Solution
{
public:int change(int amount, vector<int>& coins){int n = coins.size(); // 获取硬币种类的数量vector<unsigned long long> dp(amount + 1); // dp[j]表示组成金额j的不同组合数dp[0] = 1; // 用0个硬币组成金额0的组合方式数为1// 遍历每种硬币for(int i = 1; i <= n; i++){// 对于每个硬币，尝试更新dp数组，遍历所有金额for(int j = coins[i - 1]; j <= amount; j++) // 从当前硬币的面额开始更新dp数组{dp[j] = dp[j] + dp[j - coins[i - 1]]; // 更新dp[j]为包含当前硬币后的组合数}}// 返回组成amount的不同组合方式数return dp[amount];}
};
完全平方数
class Solution
{
public:int numSquares(int n) {// 计算小于等于n的完全平方数的数量int m = sqrt(n); // 创建dp数组，dp[i][j]表示前i个完全平方数组成金额j的最小平方数个数vector<vector<int>> dp(m + 1, vector<int>(n + 1));// 初始化dp[0][j]，表示没有完全平方数时无法组成金额jfor(int j = 1; j <= n; j++) dp[0][j] = 0x3f3f3f3f; // 0x3f3f3f3f是一个很大的数，表示无法组成金额j// 填充dp数组for(int i = 1; i <= m; i++) // 遍历每个小于等于n的完全平方数（i^2）{for(int j = 0; j <= n; j++) // 遍历每个金额j{// 默认不使用当前完全平方数i^2的情况，继承上一个完全平方数的结果dp[i][j] = dp[i - 1][j];// 如果当前金额j大于等于i^2（即当前完全平方数），则可以尝试使用该完全平方数if(j >= i * i)dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1); // 更新dp[i][j]为最小的平方数个数}}// 返回组成n的最小完全平方数个数return dp[m][n];}
};
class Solution
{
public:// numSquares方法，返回n可以表示为最少的完全平方数之和int numSquares(int n) {// 计算小于等于n的完全平方数的数量int m = sqrt(n); // 创建dp数组，dp[j]表示金额j的最小完全平方数个数vector<int> dp(n + 1);// 初始化dp数组，将每个金额的默认值设为一个较大的数，表示无法达到的状态for(int j = 1; j <= n; j++) dp[j] = 0x3f3f3f3f; // 0x3f3f3f3f 是一个大数，表示不可能组成该金额// 设置dp[0]为0，因为金额为0时，不需要任何完全平方数dp[0] = 0;// 遍历每个可能的完全平方数 i^2for(int i = 1; i <= m; i++) // i从1到sqrt(n){// 遍历每个目标金额 jfor(int j = i * i; j <= n; j++) // 从i^2开始更新dp数组{// 对于每个金额 j，尝试使用当前平方数 i^2 来更新最小平方数个数dp[j] = min(dp[j], dp[j - i * i] + 1);}}// 最终dp[n]存储了n的最小完全平方数个数，返回该值return dp[n];}
};
