day43
最后一块石头的重量Ⅱ
leetcode：1049. 最后一块石头的重量 II
动态规划
思路
a-b + c-d + e-f = (a+c+e) - (b+d+f)
等效于两堆石头相碰，最小可能重量就是最接近平均的两堆相碰。
复杂度分析
时间复杂度：O(N^2)。
空间复杂度：O(N)。
代码实现
C++：
class Solution {
public:
/*
意义：放入总重为j的商品，得到最大价值为dp[j] 商品重量、价值都为stones[i]
递推：dp[j] = max(dp[j],dp[j - stones[i]] + stones[i])
初始化：为0
遍历：先商品后背包，倒序
*/
int lastStoneWeightII(vector<int>& stones) {
// 尽量凑成相等的两堆
int sum = 0;
for(int num:stones) sum += num;
vector<int> dp(sum/2 + 1,0);
for(int i = 0;i < stones.size();i++){
for(int j = sum/2;j >= stones[i];j--){
dp[j] = max(dp[j],dp[j - stones[i]] + stones[i]);
}
}
// 相碰之后剩下大堆-小堆
return ( sum - dp[sum/2] ) - dp[sum/2];
}
};
TypeScript：
/**
类似分割等和子集
相碰之后剩下大堆减小堆
*/
function lastStoneWeightII(stones: number[]): number {
let sum = 0;
stones.forEach((num)=>sum += num);
let target = Math.floor(sum/2);
let dp = new Array(target + 1).fill(0);
for(let i = 0;i < stones.length;i++){
for(let j = target;j >= stones[i];j--){
dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
}
}
return (sum - dp[target]) - dp[target];
};
目标和
leetcode：494. 目标和
动态规划
思路
求总和为j的种类数，就是dp[j]+=dp[j-nums[i]]。
这里是组合问题，所以先遍历背包再遍历物品。
又因为可以无限取数字，所以正序遍历。
复杂度分析
时间复杂度：O(N^2)。
空间复杂度：O(N)。
代码实现
C++：
class Solution {
public:
/*
意义：总和为j的数，共有dp[j]种
递推：dp[j] += dp[j - nums[i]] 累和
初始化：dp[0] = 1 其余为0 dp[0]不表示甚麽意义，但是需要有这个滚雪球起点
遍历：先物品后背包，倒序
背包大小=(sum + target)/2
*/
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for(int num : nums) sum += num;
if(abs(target) > sum) return 0;
if((target + sum) % 2 == 1) return 0; // 背包大小决定两者之和一定是偶数才行
int bagSize = (target + sum) / 2;
vector<int> dp(bagSize + 1,0);
dp[0] = 1;
for(int i = 0;i < nums.size();i++){
for(int j = bagSize;j >= nums[i];j--){
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
}
};
TypeScript：
/**
总和为j的总共有dp[j]种
dp[j] = dp[j - nums[i]]
dp[0] = 1 ;其余为0
先物品再背包
bagSize = (target + sum) / 2
*/
function findTargetSumWays(nums: number[], target: number): number {
let sum = 0;
nums.forEach((num) => sum += num);
if(Math.abs(target) > sum) return 0;
if((target + sum) % 2 === 1) return 0; // bagSize不能为奇数
const bagSize = (target + sum) / 2;
const dp = new Array(bagSize + 1).fill(0);
dp[0] = 1;
for(let i = 0;i < nums.length;i++){
for(let j = bagSize;j >= nums[i];j--){
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
};
一和零
leetcode：474. 一和零
动态规划
二维背包，容量有两个维度。
复杂度分析：
时间复杂度：O(N^2)。
空间复杂度：O(N)。
代码实现
C++：
class Solution {
public:
/*
意义：容量为i个0和j个1的最大子集大小为dp[i][j]
递推：dp[i][j] = max(dp[i][j],dp[i-x][j-y] + 1);
初始化：全为0
遍历：物品、背包，倒序
*/
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1,(vector<int>(n+1,0)));
for(string str : strs){ // 遍历背包（确定容量）
int x = 0,y = 0;
for(char c : str){
if(c == '0') x++;
else y++;
}
// 遍历物品（）
for(int i = m;i >= x;i--){
for(int j = n;j >= y;j--){
dp[i][j] = max(dp[i][j] , dp[i-x][j-y] + 1);
}
}
}
return dp[m][n];
}
};
TS：
/**
i个0和j个1容量的最大子集的大小为dp[i][j]
dp[i][j] = max(dp[i][j],dp[i-x][j-y] + 1)
全为0
物品、背包，倒序
*/
function findMaxForm(strs: string[], m: number, n: number): number {
const dp : number[][] = new Array(m+1);
for(let i = 0;i < m+1;i++){
dp[i] = new Array(n+1).fill(0);
}
strs.forEach((str) => {
let x:number = 0, y:number = 0;
for(let char of str){
if(char === "0") x++;
else y++;
}
for(let i = m;i >= x;i--){
for(let j = n;j >= y;j--){
dp[i][j] = Math.max(dp[i][j],dp[i-x][j-y] + 1);
}
}
})
return dp[m][n];
};