322. Coin Change
322. Coin Change
思路:
https://www.youtube.com/watch?v=uUETHdijzkA
方法1: DP, 2-d 数组
这种方法浪费空间
- 易错点:第一行初始值要设为amount + 1, i.e. 一个比任何可能解都更大的数。之所以不取INT_MAX是为了防止出现INT_MAX + 1造成的overflow
- 两个向量唯独都是 n + 1, m + 1
- 但是coin和dp的纵向坐标相差1,不处理会出现heap-overflow
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<vector<int>> dp(n + 1, vector<int>(amount + 1, amount + 1));
for (int i = 0; i < n + 1; i ++){
dp[i][0] = 0;
}
for (int i = 1; i < n + 1; i ++){
for (int j = 1; j < amount + 1; j ++){
if (j - coins[i- 1] >= 0){
dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
}
else
dp[i][j] = dp[i - 1][j];
}
}
// printMatrix(dp);
return dp[n][amount] > amount ? -1 : dp[n][amount];
}
private:
void printMatrix(vector<vector<int>> & A){
for (int i = 0; i < A.size(); i++){
for (int j = 0; j < A[0].size() ; j ++){
cout << A[i][j] << " ";
}
cout << endl;
}
}
};
方法2: DP,1-d 数组
每次新一行都迭代上一行,不需要建立2-d数组
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int Max = amount + 1;
vector<int> dp(amount + 1, Max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.size(); j++) {
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
小改动
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int coin: coins){
for (int i = coin; i <= amount; i++ )
dp[i] = min(dp[i], dp[i - coin] + 1);
}
return dp[amount] > amount ? -1 : dp[amount];
}