代码随想录算法训练营第四十四天 |卡码网52. 携带研究材料 、518. 零钱兑换 II、377. 组合总和 Ⅳ
- 卡码网52. 携带研究材料
- 题目
- 解法
- 518. 零钱兑换 II
- 题目
- 解法
- 377. 组合总和 Ⅳ
- 题目
- 解法
- 感悟
卡码网52. 携带研究材料
题目
解法
题解链接
1.
#include <iostream>
#include <vector>
using namespace std;
// 先遍历背包,再遍历物品
void test_CompletePack(vector<int> weight, vector<int> value, int bagWeight) {
vector<int> dp(bagWeight + 1, 0);
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
for(int i = 0; i < weight.size(); i++) { // 遍历物品
if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
int main() {
int N, V;
cin >> N >> V;
vector<int> weight;
vector<int> value;
for (int i = 0; i < N; i++) {
int w;
int v;
cin >> w >> v;
weight.push_back(w);
value.push_back(v);
}
test_CompletePack(weight, value, V);
return 0;
}
时间复杂度:O( mn^2)
空间复杂度:O(mn )
518. 零钱兑换 II
题目
解法
题解链接
1.
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1,0);
dp[0]=1;
for(int i=0;i < coins.size(); i++){
for(int j = coins[i]; j <= amount; j++){
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
};
时间复杂度:O(mn )
空间复杂度:O(m )
377. 组合总和 Ⅳ
题目
解法
题解链接
1.
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1, 0);
dp[0] = 1;
for(int i =0; i <= target; i++){
for(int j = 0; j < nums.size(); j++){
if(i >= nums[j] && dp[i] < INT_MAX - dp[i-nums[j]]){
dp[i] += dp[i-nums[j]];
}
}
}
return dp[target];
}
};
时间复杂度:O( mn)
空间复杂度:O( m)
感悟
细节把握很重要