动态规划专题：零钱兑换、完全平方数与单词拆分求解
动态规划（Dynamic Programming, DP）是一种通过将复杂问题分解为子问题，并存储子问题的解以避免重复计算的算法范式。本文将深入探讨几个经典的动态规划问题，包括零钱兑换、完全平方数以及单词拆分，并对多重背包问题进行补充说明。
LeetCode 322. 零钱兑换
问题描述： 假设你拥有不同面额的硬币，由整数数组 coins 表示。给定一个总金额 amount，任务是计算凑成该总金额所需的最少硬币数量。如果无法凑成目标金额，则返回 -1。每种硬币的数量是无限的。
动态规划思路：
- 状态定义： 设
dp[k]表示凑成金额k所需的最少硬币数量。 - 初始状态：
dp[0] = 0，因为凑成金额 0 不需要任何硬币。对于所有其他金额k > 0，初始化dp[k]为一个极大值（例如amount + 1），表示这些金额目前还无法凑成或所需硬币数大于可能的最大值。 - 状态转移方程： 对于每一个金额
k，我们可以尝试使用每种硬币coin。如果当前硬币coin小于或等于k，并且dp[k - coin]不是极大值（即k - coin可以被凑成），那么dp[k]就可以更新为min(dp[k], dp[k - coin] + 1)。这表示凑成金额k可以通过凑成k - coin后再额外加上一个面额为coin的硬币来实现。 - 遍历顺序： 外层循环遍历硬币面额，内层循环遍历目标金额。这种顺序确保了每个硬币可以在凑成总金额时被重复使用（符合完全背包的特性）。
class Solution {
public:
int coinChange(std::vector<int>& denominations, int targetAmount) {
// minCoinsRequired[k] 存储凑成金额 k 所需的最少硬币数量
// 初始化为 targetAmount + 1，表示一个无法达到的值，比任何可能的硬币数都大
// 因为最多 targetAmount 个硬币（全部是 1 元）
std::vector<int> minCoinsRequired(targetAmount + 1, targetAmount + 1);
// 凑成金额 0 不需要硬币
minCoinsRequired[0] = 0;
// 遍历每种硬币面额
for (int coin : denominations) {
// 遍历所有可能的金额，从当前硬币面额开始
// 确保当前金额可以减去当前硬币面额
for (int currentAmount = coin; currentAmount <= targetAmount; ++currentAmount) {
// 如果 (currentAmount - coin) 可以被凑成 (即 minCoinsRequired[currentAmount - coin] 不是初始的极大值)
if (minCoinsRequired[currentAmount - coin] != targetAmount + 1) {
// 更新当前金额所需的最少硬币数
minCoinsRequired[currentAmount] = std::min(minCoinsRequired[currentAmount], minCoinsRequired[currentAmount - coin] + 1);
}
}
}
// 如果 minCoinsRequired[targetAmount] 仍然是初始的极大值，说明无法凑成目标金额
return (minCoinsRequired[targetAmount] == targetAmount + 1) ? -1 : minCoinsRequired[targetAmount];
}
};
LeetCode 279. 完全平方数
问题描述： 给定一个正整数 n，求最少需要多少个完全平方数（例如 1, 4, 9, 16, ...）才能使其和为 n。一个完全平方数是一个整数的平方，即 x*x。
动态规划思路：
此问题与"零钱兑换"问题结构高度相似。我们可以将其视为一个特殊的"零钱兑换"问题，其中"硬币"的面额是所有小于或等于 n 的完全平方数。
- 状态定义： 设
dp[k]表示凑成整数k所需的最少完全平方数数量。 - 初始状态：
dp[0] = 0。对于所有其他k > 0，初始化dp[k]为一个极大值（例如n + 1）。 - 状态转移方程： 对于每个整数
k，我们尝试用每个完全平方数square来更新dp[k]。如果square <= k且dp[k - square]不是极大值，则dp[k] = min(dp[k], dp[k - square] + 1)。 - 遍历顺序： 可以先生成所有完全平方数，然后外层遍历这些平方数，内层遍历目标和。
class Solution {
public:
int numSquares(int targetNum) {
// 生成所有小于等于 targetNum 的完全平方数
std::vector<int> perfectSquares;
for (int i = 1; i * i <= targetNum; ++i) {
perfectSquares.push_back(i * i);
}
// minSquareCounts[k] 存储凑成整数 k 所需的最少完全平方数数量
// 初始化为 targetNum + 1，表示一个无法达到的值
std::vector<int> minSquareCounts(targetNum + 1, targetNum + 1);
// 凑成整数 0 不需要完全平方数
minSquareCounts[0] = 0;
// 遍历每个完全平方数作为"物品"
for (int squareVal : perfectSquares) {
// 遍历所有可能的和，从当前完全平方数开始
for (int currentSum = squareVal; currentSum <= targetNum; ++currentSum) {
// 如果 (currentSum - squareVal) 可以被凑成
if (minSquareCounts[currentSum - squareVal] != targetNum + 1) {
// 更新当前和所需的最少完全平方数
minSquareCounts[currentSum] = std::min(minSquareCounts[currentSum], minSquareCounts[currentSum - squareVal] + 1);
}
}
}
// 根据题意，任何正整数 n 总是可以由 n 个 1 组成 (1 也是完全平方数)，
// 因此 minSquareCounts[targetNum] 不会是初始的极大值，直接返回即可。
return minSquareCounts[targetNum];
}
};
LeetCode 139. 单词拆分
问题描述： 给你一个非空字符串 s 和一个包含若干单词的字典 wordDict。判断 s 是否可以被拆分为一个或多个在字典中出现的单词。字典中的单词可以重复使用。
动态规划思路： 此问题可以看作是判断一个字符串能否通过"选择"字典中的单词来构建。
- 状态定义： 设
dp[i]是一个布尔值，表示字符串s的前i个字符（即子串s[0...i-1]）是否可以被字典中的单词拆分。 - 初始状态：
dp[0] = true。空字符串（长度为0的字符串）被认为是始终可以拆分的，这是递归的基础。 - 状态转移方程： 为了确定
dp[i]的值，我们需要向前看。如果存在某个j(0 <= j < i)，使得dp[j]为true（表示s[0...j-1]可以被拆分），并且子串s[j...i-1]存在于字典中，那么dp[i]就为true。这意味着s[0...i-1]可以被拆分为s[0...j-1]和s[j...i-1]两部分，且这两部分都符合条件。 - 遍历顺序： 外层循环遍历字符串的结束位置
i(从 1 到s.size())，内层循环遍历所有可能的分割点j(从 0 到i-1)。
class Solution {
public:
bool wordBreak(std::string inputString, std::vector& dictionary) {
// 将字典中的单词放入哈希集合，以便 O(1) 时间复杂度查找
std::unordered_set dictSet(dictionary.begin(), dictionary.end());
// canSegment[i] 表示 inputString 的前 i 个字符能否被拆分
std::vector<bool> canSegment(inputString.size() + 1, false);
// 空字符串可以被拆分 (作为递归的基准)
canSegment[0] = true;
// 遍历字符串的每个可能的结束位置 (从长度 1 到 inputString.size())
for (int endIndex = 1; endIndex <= inputString.size(); ++endIndex) {
// 遍历所有可能的分割点 (从 0 到 endIndex - 1)
for (int startIndex = 0; startIndex < endIndex; ++startIndex) {
// 如果 inputString 的前 startIndex 个字符可以被拆分 (canSegment[startIndex] 为 true)
// 并且从 startIndex 到 endIndex-1 的子串在字典中
if (canSegment[startIndex] && dictSet.count(inputString.substr(startIndex, endIndex - startIndex))) {
canSegment[endIndex] = true; // 那么 inputString 的前 endIndex 个字符也可以被拆分
break; // 找到一个有效拆分即可，无需继续遍历 startIndex
}
}
}
return canSegment[inputString.size()];
}
};
多重背包问题
问题描述： 假设有一个容量为 C 的背包。现有 N 种物品，每种物品 i 有其重量 w[i]、价值 v[i]，并且最多有 k[i] 个可用。目标是在不超过背包容量的前提下，最大化所能获得的总价值。
动态规划思路：
多重背包问题是 0/1 背包问题的变种，每种物品不再是只能选一次，而是可以选多次，但有数量上限。有两种常见的解法：
方法一：转化为 0/1 背包问题
最直接的方法是将每种数量为 k[i] 的物品 i 展开成 k[i] 个完全独立的物品，然后像 0/1 背包问题那样处理。例如，如果物品 A 有 3 个可用，就创建 3 个独立的物品 A1, A2, A3，它们都具有物品 A 的重量和价值。
然而，更高效的方法是使用二进制拆分（Binary Splitting），将物品 i 的 k[i] 个数量拆分为若干个物品，它们的数量是 1, 2, 4, ..., 2p, 以及剩余的部分，这样可以有效减少物品总数。下面示例代码展示的是一种简单的展开方式，即将多个同种物品直接添加到物品列表中：
#include <iostream>
#include <vector>
#include <algorithm> // for std::max
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int capacity, numOriginalItems;
std::cin >> capacity >> numOriginalItems;
std::vector<int> originalWeights(numOriginalItems);
std::vector<int> originalValues(numOriginalItems);
std::vector<int> originalCounts(numOriginalItems);
for (int i = 0; i < numOriginalItems; ++i) std::cin >> originalWeights[i];
for (int i = 0; i < numOriginalItems; ++i) std::cin >> originalValues[i];
for (int i = 0; i < numOriginalItems; ++i) std::cin >> originalCounts[i];
// 将多重背包问题展开为 0/1 背包问题
std::vector<int> expandedWeights;
std::vector<int> expandedValues;
for (int i = 0; i < numOriginalItems; ++i) {
int currentCount = originalCounts[i];
while (currentCount > 0) {
expandedWeights.push_back(originalWeights[i]);
expandedValues.push_back(originalValues[i]);
currentCount--;
}
}
// maxValues[j] 表示背包容量为 j 时可以获得的最大价值
std::vector<int> maxValues(capacity + 1, 0);
// 0/1 背包的核心逻辑
for (int itemIdx = 0; itemIdx < expandedWeights.size(); ++itemIdx) {
int currentWeight = expandedWeights[itemIdx];
int currentValue = expandedValues[itemIdx];
// 倒序遍历容量，确保每件展开的"物品"只被选择一次
for (int currentCapacity = capacity; currentCapacity >= currentWeight; --currentCapacity) {
maxValues[currentCapacity] = std::max(maxValues[currentCapacity], maxValues[currentCapacity - currentWeight] + currentValue);
}
}
std::cout << maxValues[capacity] << std::endl;
return 0;
}
方法二：嵌套循环遍历
另一种直接的方法是在 0/1 背包的框架内，为每种物品额外增加一个循环来遍历该物品可以选择的数量。对于每种物品 i，我们可以选择 0 到 k[i] 个。
#include <iostream>
#include <vector>
#include <algorithm> // for std::max
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int capacity, numItems;
std::cin >> capacity >> numItems;
std::vector<int> itemWeights(numItems);
std::vector<int> itemValues(numItems);
std::vector<int> itemCounts(numItems);
for (int i = 0; i < numItems; ++i) std::cin >> itemWeights[i];
for (int i = 0; i < numItems; ++i) std::cin >> itemValues[i];
for (int i = 0; i < numItems; ++i) std::cin >> itemCounts[i];
// maxValues[j] 表示背包容量为 j 时可以获得的最大价值
std::vector<int> maxValues(capacity + 1, 0);
// 遍历每种物品
for (int i = 0; i < numItems; ++i) {
int currentWeight = itemWeights[i];
int currentValue = itemValues[i];
int currentCount = itemCounts[i];
// 倒序遍历背包容量，确保物品 i 的每次选择都基于上一个物品或当前物品的上一个状态
for (int currentCapacity = capacity; currentCapacity >= currentWeight; --currentCapacity) {
// 额外循环遍历当前物品可以选择的数量
for (int k = 1; k <= currentCount; ++k) {
// 如果选择 k 个当前物品后，背包容量仍足够
if (currentCapacity - k * currentWeight >= 0) {
maxValues[currentCapacity] = std::max(maxValues[currentCapacity], maxValues[currentCapacity - k * currentWeight] + k * currentValue);
} else {
// 如果再多选一个就会超重，则无需继续增加数量
break;
}
}
}
}
std::cout << maxValues[capacity] << std::endl;
return 0;
}
