322零钱兑换
力扣题目链接
题目描述：
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins =[1, 2, 5], amount =11输出：3解释：11 = 5 + 5 + 1
示例 2：
输入：coins =[2], amount =3输出：-1
示例 3：
输入：coins = [1], amount = 0 输出：0
代码·：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// 创建一个大小为 amount + 1 的向量 dp，初始化为 amount + 1。
// 这里使用 amount + 1 是因为这是一个无法达到的最大值 (相当于无穷大)。
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0; // 当金额为0时，需要0个硬币。
// 遍历所有的硬币面额
for (int i = 0; i < (); i++) {
// 对于每种硬币面额，更新 dp 表，以此每次可以选择当前硬币。
for (int j = coins[i]; j <= amount; j++) {
// 这里选择当前硬币，并且计算选择当前硬币后可能达到的最小硬币数
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
// 如果 dp[amount] 仍然是 amount + 1，说明无法凑成目标金额，返回 -1；
// 否则，返回组成目标金额的最小硬币数。
return dp[amount] > amount ? -1 : dp[amount];
}
}; /*dp[j] = min(dp[j], dp[j - coins[i]] + 1); 这段代码的性质：
dp[j]只有在合法的数据上+1才算是合法，dp数组里的所有的合法的数据都是在 dp[j - coins[i]] + 1合法的基础上得来的，如果 dp[j - coins[i]] + 1不合法，意思就是 dp[j - coins[i]] + 1=amount+2，此时dp[j]不变，还是amount+1，只有在dp[j - coins[i]]这个数据合法（就是小于不可能值amount+1）时才能进行数据的覆盖*/
1. 确定 dp 数组以及下标和对应值的含义
- dp 数组：dp[i] 表示凑成金额 i 所需的最少硬币个数。
- 下标 i：表示金额。
- dp[i] 值：最少的硬币数量，如果无法凑成该金额，初始化为一个无法到达的最大值，即 amount + 1。
2. 确定递推公式
-
公式：
dp[j] = min(dp[j], dp[j - coins[i]] + 1) -
含义：不使用当前硬币
coins[i]时，所需的硬币数为dp[j]；使用当前硬币时，需要再加上一个coins[i]，递推出dp[j - coins[i]] + 1。
3. dp 数组如何初始化
- 初始化为
dp[0] = 0，因为金额为0时不需要硬币。 - 其余的 dp 值初始化为
amount + 1，代表无法达成或不可达（等效于无穷大）。
4. 确定遍历顺序
-
外层循环：遍历每种硬币（
for (int i = 0; i < (); i++)），以便更新 dp 数组。 -
内层循环：从当前硬币的面额开始遍历到目标金额（
for (int j = coins[i]; j <= amount; j++)），更新可以凑成金额 j 的最少硬币个数。
5. 举例推导 dp 数组
假设 coins = [1, 2, 5]，amount = 11。
-
初始化：
dp = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf] -
使用面额 1：
- 更新 dp 值：
dp = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
- 更新 dp 值：
-
使用面额 2：
- 更新 dp 值：
dp = [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
- 更新 dp 值：
-
使用面额 5：
- 更新 dp 值：
dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
- 更新 dp 值：
最后，dp[11] = 3，表示使用面额 [1, 2, 5] 可以凑成11的最少硬币数量为3（例如 5 + 5 + 1）。
279完全平方数
力扣题目链接
题目描述：
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n =12输出：3 解释：12 = 4 + 4 + 4
示例 2：
输入：n =13输出：2 解释：13 = 4 + 9
代码：（跟上一题一摸一样，不再过多赘述）
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1,n+1);
dp[0]=0;
dp[1]=1;
for(int i=1;i<n;i++){
for(int j=i*i;j<=n;j++){
dp[j]=min(dp[j],dp[j-i*i]+1);
}
}
return dp[n]>n? -1 : dp[n];
}
};139单词拆分
力扣题目链接
题目描述：
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
// 将 wordDict 中的单词放入一个集合 wordSet 中，以便快速查找。
set<string> wordSet((), ());
// 创建一个布尔型的 dp 数组，表示直到索引 i 的子字符串 s[0...i-1] 是否可以被字典中的单词组合而成。
vector<bool> dp(() + 1, false);
// 空字符串可以被认为是可以被组合而成的，故 dp[0] 初始化为 true。
dp[0] = true;
// 遍历字符串 s 的每一个位置，计算到该位置是否可以被字典单词组合而成。
for (int i = 1; i <= (); i++) { // 遍历“背包”（即目标字符串的内容）
for (int j = 0; j < i; j++) { // 遍历“物品”（即目标字符串的前缀子字符串）
// 从索引 j 开始，截取长度为 (i-j) 的字符串。
string word = (j, i - j);
// 检查当前子串 word 是否在字典中，并且 dp[j] 为 true，表示 [0...j) 这一子串可被组合而成。
if ((word) != () && dp[j]) {
dp[i] = true; // 如果条件满足，设置 dp[i] 为 true (当前子串 [0...i) 可以被组合而成)
break; // 找到可以组合方式后，结束本轮内部循环
}
}
}
// 返回 dp 最后一个位置的值，这反映了整个字符串是否可以被组合而成。
return dp[()];
}
};1. 确定 dp 数组以及下标和对应值的含义
- dp 数组：dp[i] 表示子字符串 s[0...i-1] 是否可以被字典中的单词组合而成。
- 下标 i：表示字符串中位置 (从 1 开始)，即上限是第i个子串。
- dp[i] 值：布尔值，表明 s[0...i-1] 是否能够由字典中的单词组成。
2. 确定递推公式
-
公式：
dp[i] = true if ∃ j (0 ≤ j < i), dp[j] && (s[j...i-1] ∈ wordSet) - 含义：如果从索引 j 到 i-1 的子串是字典中的单词，并且 s[0...j-1] 可以被组合而成，那 s[0...i-1] 也可以组合而成。
3. dp 数组如何初始化
- dp[0] = true，因为空字符串可以被认为是已组合完成。
4. 确定遍历顺序
- 外层循环：i 从 1 到 ()，代表当前考核的终止位置。
- 内层循环：j 从 0 到 i-1，考察前 j 个字符是否可以被组合而成及其后的字符组合可能。
5. 举例推导 dp 数组
假设 s = "leetcode"，wordDict = ["leet", "code"]。
dp = [true, false, false, false, true, false, false, false, true]- 解释推导：
-
dp[0] = true（空字符串被认为可以组合） - 从 j=0 到 j=3，"leet" 在 wordDict 中，所以
dp[4] = true - 从 j=4 到 j=7，对于
s[4..7]，即 "code"，也是在 wordDict 中，dp[8] = true
-
最终，dp[8] = true，说明整个字符串可以被组合而成。
if ((word) != () && dp[j]) {
dp[i] = true;
而&&dp[j] 就是判断这个字符串是否连接上了，而不是单独的判断这个截取的字段存在不存在
与dp[j - coins[i]] + 1有异曲同工之处