代码随想录算法训练营第44天|动态规划：完全背包理论基础、518.零钱兑换II、377. 组合总和 Ⅳ

动态规划：完全背包理论基础

518.零钱兑换II

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

用一个二维dp数组

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

用一维

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

377. 组合总和 Ⅳ

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

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1, 0);dp[0] = 1;for (int j = 0; j <= target; 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];}
};