563. Backpack V 不重复使用
int backPackV(vector<int> &nums, int target) {
// write your code here
// 和coins不同之处是，这里每个元素只能用一次
const int size = nums.size();
if(size == 0 || target == 0){
return 0;
}
vector<vector<int>> dp(target + 1, vector<int>(size + 1, 0));
dp[0][0] = 1;
for(int j = 1; j <= size; j++){
dp[0][j] = 1;
}
for(int i = 1; i <= target; i++){
for(int j = 1; j <= size; j++){
if(i >= nums[j - 1]){
dp[i][j] = dp[i - nums[j - 1]][j - 1] + dp[i][j - 1]; //这里是和coin change不一样的地方，dp[i - nums[j - 1]][j]
//其实就可以转成一维数组了。[j]只和之前的j - 1有关。
}
else{
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[target][size];
}
Comments
Post a Comment