代码随想录算法训练营第三十七天 | 动态规划 part05

518.零钱兑换II

问题的本质就是给定一个容量的背包，装满有多少种方法，递推公式是：dp[j] += dp[j - coins[i]]
但是这里有拓展的地方是遍历顺序，完全背包问题是可以调换两个for循环的顺序的，但是在这里不行。因为这里是组合问题，要先遍历物品，再遍历背包。如果是排列问题，要先遍历背包，再遍历物品。
对于先遍历物品，再遍历背包的遍历顺序来说，每次只会多去更新一个物品。类似于组合。
但是对于先遍历背包，再遍历物品的遍历顺序来说，每次都会从头区遍历物品，类似于排序。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // 1. dp[j] 表示凑成总金额为j有dp[j]种方法
        // 2. 递推公式：dp[j] += dp[j - coins[i]]
        // 3. 初始化：dp[0] = 1, 其余为0

        vector<int> dp(amount + 1, 0);
        dp[0] = 1;

        for (int i = 0; i < coins.size(); ++i) {
            for (int j = coins[i]; j < amount + 1; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }

        return dp[amount];
    }
};

377. 组合总和 Ⅳ

这一题就是求得排列，与上题的区别就是for循环位置。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // 1. dp[j] 表示凑成目标整数为j有dp[j]种方法
        // 2. 递推公式：dp[j] += dp[j - nums[i]]
        // 3. 初始化：dp[0] = 1, 其余为0

        vector<int> dp(target + 1, 0);
        dp[0] = 1;

        for (int j = 0; j < target + 1; j++) {
            for (int i = 0; i < nums.size(); ++i) {
                if (j >= nums[i] && dp[j] < INT_MAX - dp[j - nums[i]])
                    dp[j] += dp[j - nums[i]];
            }
        }

        return dp[target];
    }
};

57. 爬楼梯

可以将爬楼梯抽象为完全背包问题。背包容量是楼梯数，物品的重量就是1-m，每次爬多少级台阶，物品的价值是爬到j台阶数有多少种方法。在本题中，是一种排列问题，而不是组合问题。

#include <iostream>
#include <vector>

using namespace std;

void completebag() {
    int target, step;
    cin >> target >> step;
    
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    
    for (int j = 0; j < target + 1; j++) {
        for (int i = 1; i < step + 1; ++i) {
            if (j >= i)
                dp[j] += dp[j - i];
        }
    }
    cout << dp[target];
}

int main() {
    completebag();
    return 0;
}