669. Coin Change

注意这里用的一维dp vector，但需要额外的判断条件dp[i - coins[j]] != INT_ MAX

int coinChange(vector<int> &coins, int amount) { // write your code here const int size = coins.size(); if(size == 0){ return 0; } vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; for(int i = 1; i <= amount; i++){ for(int j = 0; j < size; j++){ if(i >= coins[j] &&dp[i - coins[j]] != INT_ MAX){
int tmp = dp[i - coins[j]] + 1; dp[i] = min(dp[i], tmp); } } } return dp[amount] == INT_MAX ? -1 : dp[amount]; }

如果是用二维的，会是更general的方法，可用于解决 coin change II的问题。
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, amount + 1)); dp[0][0] = 0; for(int i = 1; i <= amount; i++){ for(int j = 1; j <= size; j++){ dp[0][j] = 0; if(i >= coins[j - 1]){ //int tmp = ; dp[i][j] = min(dp[i - coins[j - 1]][j] + 1, dp[i][j - 1]); } else{ dp[i][j] = dp[i][j - 1]; } } } return dp[amount][size] == amount + 1 ? -1 : dp[amount][size]; }