322. 零钱兑换

题目链接：https://leetcode.cn/problems/coin-change/
文章讲解：https://programmercarl.com/0322.零钱兑换.html
题目难度：中等
视频讲解：https://www.bilibili.com/video/BV14K411R7yv/
题目状态：略微有点思路，但还是有点转不过来。

思路：

这次是找最小的钱币组合，因此在进行 dp 数组初始化的时候需要将其初始化为最大值（INT_MAX）。
接着就是和之前的背包问题套路一样，但是要注意的是：

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

代码：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for(int i = 0; i < coins.size(); ++i) {
            for(int j = coins[i]; j <= amount; ++j) {
                if(dp[j - coins[i]] != INT_MAX) {
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        if(dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

279. 完全平方数

题目链接：https://leetcode.cn/problems/perfect-squares/
文章讲解：https://programmercarl.com/0279.完全平方数.html
题目难度：中等
视频讲解：https://www.bilibili.com/video/BV12P411T7Br/
题目状态：看题解，平方数给我整懵了

思路：

套路和上面是一样的，只是“物体”变成了完全平方数。

代码：

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX); // 初始化一个大小为 n+1 的数组，所有值为 INT_MAX
        dp[0] = 0; // 0 需要 0 个完全平方数
        for(int i = 1; i <= n; ++i) { // 遍历 1 到 n
            for(int j = 1; j * j <= i; ++j) { // 遍历所有小于等于 i 的平方数
                dp[i] = min(dp[i], dp[i - j * j] + 1); // 更新 dp[i] 的最小值
            }
        }
        return dp[n]; // 返回 dp[n]，即 n 的最小完全平方数数量
    }
};

139. 单词拆分

题目链接：https://leetcode.cn/problems/word-break/
文章讲解：https://programmercarl.com/0139.单词拆分.html
题目难度：中等
视频讲解：https://www.bilibili.com/video/BV1pd4y147Rh/
题目状态：难啊

标签：遍历,part6,int,随想录,vector,https,com,dp,第三十三
From： https://www.cnblogs.com/frontpen/p/18350318