代码随想录day38|| 322零钱兑换 279完全平方数 139单词拆分

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 < coins.size(); 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 < coins.size(); 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]

• 使用面额 2：

  • 更新 dp 值：dp = [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]

• 使用面额 5：

  • 更新 dp 值：dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]

最后，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(wordDict.begin(), wordDict.end());  
        
        // 创建一个布尔型的 dp 数组，表示直到索引 i 的子字符串 s[0...i-1] 是否可以被字典中的单词组合而成。  
        vector<bool> dp(s.size() + 1, false);  
        
        // 空字符串可以被认为是可以被组合而成的，故 dp[0] 初始化为 true。  
        dp[0] = true;  
        
        // 遍历字符串 s 的每一个位置，计算到该位置是否可以被字典单词组合而成。  
        for (int i = 1; i <= s.size(); i++) {   // 遍历“背包”（即目标字符串的内容）  
            for (int j = 0; j < i; j++) {       // 遍历“物品”（即目标字符串的前缀子字符串）  
                // 从索引 j 开始，截取长度为 (i-j) 的字符串。  
                string word = s.substr(j, i - j);  
                // 检查当前子串 word 是否在字典中，并且 dp[j] 为 true，表示 [0...j) 这一子串可被组合而成。  
                if (wordSet.find(word) != wordSet.end() && dp[j]) {  
                    dp[i] = true;  // 如果条件满足，设置 dp[i] 为 true (当前子串 [0...i) 可以被组合而成)  
                    break;  // 找到可以组合方式后，结束本轮内部循环  
                }  
            }  
        }  
        
        // 返回 dp 最后一个位置的值，这反映了整个字符串是否可以被组合而成。  
        return dp[s.size()];  
    }  
};

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 到 s.size()，代表当前考核的终止位置。
• 内层循环：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 (wordSet.find(word) != wordSet.end() && dp[j]) {  
                    dp[i] = true;

而&&dp[j] 就是判断这个字符串是否连接上了，而不是单独的判断这个截取的字段存在不存在

与dp[j - coins[i]] + 1有异曲同工之处