740. Coin Change 2

int change(int amount, vector<int> &coins) { // write your code here // DP state: DP[i][j] the number of combinations regarding to the amount of i given first j coins. (It does not mean the j-th element must be used) // transition: if(coins[j] <= i) dp[i] = dp[i - coins[j - 1]][j] + dp[i][j - 1]; //可重复使用 // // int coinChange(vector<int> &coins, int amount) { // write your code here const int size = coins.size(); if(size == 0){ return 0; } if(amount == 0){ return 0; } vector<vector<int>> dp(amount + 1, vector<int>(size + 1, 0)); dp[0][0] = 1; for(int i = 1; i <= amount; i++){ for(int j = 1; j <= size; j++){ dp[0][j] = 1; // if(i >= coins[j - 1]){ //int tmp = ; dp[i][j] = (dp[i - coins[j - 1]][j]) + dp[i][j - 1]; //放和不放 } else{ dp[i][j] = dp[i][j - 1]; } } } return dp[amount][size]; }



另一种 只用一维的vector
int change(int amount, vector<int> &coins) { // write your code here // DP state: DP[i][j] the number of combinations regarding to the amount of i given first j coins. (It does not mean the j-th element must be used) // transition: if(coins[j] <= i) dp[i] = dp[i - coins[j - 1]][j] + dp[i][j - 1]; //可重复使用 // // int coinChange(vector<int> &coins, int amount) { // write your code here const int size = coins.size(); if(size == 0){ return 0; } if(amount == 0){ return 0; } //vector<vector<int>> dp(amount + 1, vector<int>(size + 1, 0)); //dp[0][0] = 1; //用一维dp state做法 vector<int> dp(amount + 1, 0); dp[0] = 1; for(int j = 0; j < size; j++){ //顺序得变化，否则出现233,332，这种重复的combination for(int i = coins[j]; i <= amount; i++){ //dp[0][j] = 1; // dp[i] += dp[i - coins[j]]; //if(i >= coins[j - 1]){ //int tmp = ; // dp[i][j] = (dp[i - coins[j - 1]][j]) + dp[i][j - 1]; //放和不放 //} //else{ // dp[i][j] = dp[i][j - 1]; //} } } return dp[amount]; }