和knapsack problem类似的问题,这里求的就是要让背包正好填满所需的最少物品数量。每物品可以用无限多个,所以就是无界背包问题。用DP[i][j]表示用前i + 1个物品填满容量为j的背包所需的最少物品数量,c[i]为第i + 1个物品的体积。那么递推公式为;
- DP[i][j] = min(DP[i - 1][j], DP[i][j - c[i]] + 1)
假设体积为V,物品数量为n,时间复杂度为O(n * V),空间复杂度可以优化为O(V),代码如下:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
int coinChange(vector<int>& coins, int amount) { | |
if(!amount)return 0; | |
int n = coins.size(); | |
vector<int> dp(amount + 1, amount + 1); | |
dp[0] = 0; | |
for(int i = 0; i < n; ++i) | |
{ | |
int coin = coins[i]; | |
for(int j = coin; j <= amount; ++j) | |
{ | |
dp[j] = min(dp[j], 1 + dp[j - coin]); | |
} | |
} | |
return dp[amount] <= amount? dp[amount]: -1; | |
} | |
}; |
这道题递推公式可以有很多种,比如用DP[i]表示填满容量为i的背包所需的最少物品数量,我们还可以得到另一个递推公式:
- DP[i] = min(DP[i - c[j]] + 1), where c[j]为第j + 1个物品的体积,且c[j] <= i
时间复杂度和空间复杂度同上,代码如下:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
int coinChange(vector<int>& coins, int amount) { | |
int len = coins.size(); | |
vector<int> dp(amount + 1, amount + 1); | |
dp[0] = 0; | |
for(int i = 1; i <= amount; ++i) | |
{ | |
for(int j = 0; j < len; ++j) | |
{ | |
int coin = coins[j]; | |
if(coin <= i) | |
dp[i] = min(dp[i], dp[i - coin] + 1); | |
} | |
} | |
return dp[amount] == amount + 1? -1: dp[amount]; | |
} | |
}; |
No comments:
Post a Comment