LeetCode刷题day29——动态规划（完全背包）

377. 组合总和 Ⅳ

https://leetcode.cn/problems/combination-sum-iv/

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• nums 中的所有元素 互不相同
• 1 <= target <= 1000

**进阶：**如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

分析：

注意这里的溢出报错：dp[i] + dp[i - nums[j]]不能被表示,会直接报错

 // if (i - nums[j] >= 0 && dp[i] + dp[i - nums[j]] <
                    // INT_MAX) overflow: 2147483646 + 1073741824 cannot be
                    // represented in type 'value_type' (aka 'int')
                    // (solution.cpp)

• 如果先物品后容量，是排列（上一题
• 先容量后物品，是组合（讲顺序

如果把遍历 nums（物品）放在外层循环，target 放在内层循环，举个例子：计算 dp[4] 时，结果集只会包含 {1, 3} 这样的组合，而不会有 {3, 1}，因为外层循环的 nums 顺序固定，3 必须在 1 后面。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        // 如果先物品后容量，是排列
        // 先容量后物品，是组合（讲顺序
        for (int i = 0; i <= target; i++) {         // 容量
            for (int j = 0; j < nums.size(); j++) { // 物品
                if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]])
                    // if (i - nums[j] >= 0 && dp[i] + dp[i - nums[j]] <
                    // INT_MAX) overflow: 2147483646 + 1073741824 cannot be
                    // represented in type 'value_type' (aka 'int')
                    // (solution.cpp)
                    dp[i] = dp[i] + dp[i - nums[j]];
            }
        }
        return dp[target];
    }
};

57. 爬楼梯（第八期模拟笔试）

https://kamacoder.com/problempage.php?pid=1067

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

输入描述

输入共一行，包含两个正整数，分别表示n, m

输出描述

输出一个整数，表示爬到楼顶的方法数。

输入示例

3 2

输出示例

3

提示信息

数据范围：
1 <= m < n <= 32;

当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。

此时你有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶段
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

分析：

楼梯总阶数n作为容量，from 0 to n（列）

至多能爬m阶作为物品，from 1 to m（行）

• 动态规划方程： dp[i] = dp[i] + d[i-v[i]];

求组合，所以先遍历容量，而且动态规划方程是跟着容量一起变化的

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> v(m);
    for (int i = 0; i < m; i++)
        v[i] = i + 1;
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            if (i - v[j] >= 0)
                dp[i] += dp[i - v[j]];//注意，这里是外层的下标
        }
    }
    cout << dp[n] << endl;

    return 0;
}

322. 零钱兑换

https://leetcode.cn/problems/coin-change/

给你一个整数数组 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

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

分析：

示例1的填表过程：

• 动态规划方程： dp[j] = min(1 + dp[j - coins[i]], dp[j]);

​ 本硬币i加入 不加入这块硬币

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

279. 完全平方数

https://leetcode.cn/problems/perfect-squares/)

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

• 1 <= n <= 104

分析：

没什么好分析的，前面的会了，这题秒。

class Solution {
public:
    int numSquares(int n) {
        int num = ceil(sqrt(n));
        vector<int> dp(n + 1, INT_MAX - 1);
        vector<int> nums(num, 0);
        for (int i = 0; i < num; i++)
            nums[i] = (i + 1) * (i + 1);

        dp[0] = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < num; j++) {
                if (i >= nums[j])
                    dp[i] = min(dp[i - nums[j]] + 1, dp[i]);
            }
        }
        return dp[n];
    }
};

139. 单词拆分

https://leetcode.cn/problems/word-break/)

给你一个字符串 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

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 仅由小写英文字母组成
• wordDict 中的所有字符串 互不相同

分析：

该算法使用 动态规划 来判断给定的字符串 s 是否可以被分割为若干个字典中的单词。

1. 动态规划数组 dp：
   • 定义一个布尔型数组 dp，其中 dp[i] 表示字符串 s[0...i-1] 是否可以由字典中的单词组成。
   • 初始化 dp[0] = true，表示空字符串可以被分割。
2. 状态转移：
   • 遍历字符串 s 的每个位置 i，如果 dp[i] 为 true（即 s[0...i-1] 可以被分割），则继续向后查找可能的子字符串 s[i...j-1]，并判断该子字符串是否存在于字典中。
   • 如果存在该单词，则将 dp[j] 设置为 true，表示 s[0...j-1] 可以由字典中的单词组成。
3. 返回结果：
   • 最终，dp[len] 表示整个字符串 s 是否可以由字典中的单词组成，返回 dp[len] 即可。

• 也就是说：如果 dp[j] 为 true 且 s[j, i] 在字典中，则 dp[i] = true。其中，j < i。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int len = s.size();
        vector<bool> dp(len + 1, false);
        dp[0] = true;
        for (int i = 0; i <= len; i++) {
            if (dp[i]) {
                for (int j = i + 1; j <= len; j++) {
                    string word = s.substr(i, j - i);
                    int flag = 0;
                    for (int k = 0; k < wordDict.size(); k++) {
                        if (wordDict[k] == word) {
                            flag = 1;
                            break;
                        }
                    }
                    if (flag == 1)
                        dp[j] = true;
                }
            }
        }
        return dp[len];
    }
};