leetcode：518. 零钱兑换 II[完全背包]

学习要点

1. 理解完全背包思想
2. 理解一维数组的解法

题目链接

        518. 零钱兑换 II - 力扣（LeetCode）

题目描述

解法：二维数组

class Solution {
public:int change(int amount, vector<int>& coins) {if (amount == 0)return 1;// dp[i][j]  0-i中任意无限取凑成j的最大方式int n = coins.size();vector<vector<uint64_t >> dp(n, vector<uint64_t>(amount + 1, 0));// 初始化for (int i = 1; i <= amount; i++) {if (i % coins[0] == 0) {dp[0][i] = 1;}}for (int i = 0; i < n; i++) {dp[i][0] = 1;}// 开始动归for (int i = 1; i < n; i++) {for (int j = 1; j <= amount; j++) {if (coins[i] > j) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];}}}return dp[n - 1][amount];}
};

解法：一维数组

class Solution {
public:int change(int amount, vector<int>& coins) {// 完全背包组合问题if(amount == 0) return 1;int n = coins.size();vector<uint64_t> dp(amount+1,0);// dp[j] = dp[j]上一层 + dp[j-coins[i]]这一层 dp[0] = 1;for(int i = 0;i<n;i++){for(int j = coins[i];j<=amount;j++){dp[j] += dp[j-coins[i]]; }}return dp[amount];}
};