海外广告投放平台_制作小程序和网站的公司_最新地址_2024疫情最新消息今天

第九章 动态规划 part06

322. 零钱兑换

如果求组合数就是外层 for 循环遍历物品，内层 for 遍历背包。
如果求排列数就是外层 for 遍历背包，内层 for 循环遍历物品。

这句话结合本题，大家要好好理解。

• 视频讲解：B站链接
• 题解链接：程序员Carl - 零钱兑换
  代码也是很好理解呢

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX));dp[0]=0;for (int coin : coins) { // 遍历物品   for (int j = coin; j <= amount; j++) { dp[j] = min(dp[j], dp[j - coin] + 1);}}if(dp[amount]==INT_MAX))return -1;return dp[amount];}};

首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;

其他下标对应的数值呢？

考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

279. 完全平方数

本题和 322. 零钱兑换 基本是一样的，大家可以先自己尝试做一做。

• 视频讲解：B站链接
• 题解链接：程序员Carl - 完全平方数

class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1, INT_MAX);std::vector<int> squares;// 将 1 的平方到 100 的平方依次添加到 vector 中for (int i = 1; i*i <= n; ++i) squares.push_back(i * i);dp[0]=0;for (int square : squares) { // 遍历物品   for (int j = square; j <= n; j++) { dp[j] = min(dp[j], dp[j - square] + 1);}}return dp[n];}
};

这题和上一题几乎完全一模一样，不过平方数数组需要自己去设计，整体难度不高。

139. 单词拆分

• 视频讲解：B站链接
• 题解链接：程序员Carl - 单词拆分

---

这题的思路还是很清晰的，就是很直观的想法，其实感觉动态规划都没有用多少，就是单纯用BOOL数组标记点，一遍遍的去遍历。

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int i = 1; i <= s.size(); i++) {   // 遍历背包for (int j = 0; j < i; j++) {       // 遍历物品string word = s.substr(j, i - j); //substr(起始位置，截取的个数)if (wordSet.find(word) != wordSet.end() && dp[j]) {dp[i] = true;}}}return dp[s.size()];}
};

回溯法：回溯法通过递归尝试每一个可能的分割点。我们从字符串的第一个字符开始，尝试所有可能的前缀是否在字典中。如果找到一个前缀在字典中，则递归继续检查剩余部分的字符串，直到字符串的每一部分都能在字典中找到，或者尝试所有可能的分割失败。

class Solution {
private:bool backtracking (const string& s, const unordered_set<string>& wordSet, int startIndex) {if (startIndex >= s.size()) {return true;}for (int i = startIndex; i < s.size(); i++) {string word = s.substr(startIndex, i - startIndex + 1);if (wordSet.find(word) != wordSet.end() && backtracking(s, wordSet, i + 1)) {return true;}}return false;}
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());return backtracking(s, wordSet, 0);}
};

函数 backtracking 通过递归的方式，检查从 startIndex 开始的字符串能否通过字典中的单词拼接。
从 startIndex 开始，遍历到字符串末尾，逐渐增加子串长度。s.substr(startIndex, i - startIndex + 1) 提取从 startIndex 到 i 的子串。
例如，对于 s = “leetcode”，当 startIndex = 0 时，子串依次为 “l”, “le”, “lee”, “leet” 等。如果提取的子串 word 在字典中，则进一步递归调用 backtracking(s, wordSet, i + 1)，检查剩下的部分是否也能通过字典中的单词拼接。
如果递归返回 true，意味着找到了一条完整的分割路径，因此立即返回 true。
太久没看回溯算法，生疏的很。
递归的过程中有很多重复计算，可以使用数组保存一下递归过程中计算的结果。

这个叫做记忆化递归，这种方法我们之前已经提过很多次了。

使用memory数组保存每次计算的以startIndex起始的计算结果，如果memory[startIndex]里已经被赋值了，直接用memory[startIndex]的结果。

class Solution {
private:bool backtracking (const string& s,const unordered_set<string>& wordSet,vector<bool>& memory,int startIndex) {if (startIndex >= s.size()) {return true;}// 如果memory[startIndex]不是初始值了，直接使用memory[startIndex]的结果if (!memory[startIndex]) return memory[startIndex];for (int i = startIndex; i < s.size(); i++) {string word = s.substr(startIndex, i - startIndex + 1);if (wordSet.find(word) != wordSet.end() && backtracking(s, wordSet, memory, i + 1)) {return true;}}memory[startIndex] = false; // 记录以startIndex开始的子串是不可以被拆分的return false;}
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> memory(s.size(), 1); // -1 表示初始化状态return backtracking(s, wordSet, memory, 0);}
};

memory 数组是用来记录从某个位置 startIndex 开始的子字符串是否可以成功拆分成字典中的单词组合。它的作用主要是缓存中间结果，避免重复计算。

在 wordBreak 函数中，memory 被初始化为一个大小为 s.size() 的布尔数组，初始值为 true。这里的 true 并不表示某个位置的子串可以被拆分，而是表示这个位置的子问题尚未被计算过。

当回溯函数发现从 startIndex 开始的子串无法被有效拆分时，它会将 memory[startIndex] 设置为 false，表示从该位置无法完成拆分，后续不需要再尝试。
如果某个位置可以成功拆分，则直接返回 true，后续如果再次回到该位置，可以立即使用之前的计算结果。

背包问题总结篇！

• 题解链接：程序员Carl - 背包总结篇