[Algorithm][动态规划][01背包问题][目标和][最后一块石头的重量Ⅱ]详细讲解
目录
- 1.目标和
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
- 2.最后一块石头的重量 II
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
1.目标和
1.题目链接
- 目标和
2.算法原理详解
-
问题转化:在数组中选择一些数,让这些数的和等于
a
,一共有多少种选法?–> 01背包
-
思路:
-
确定状态表示 ->
dp[i][j]
的含义dp[i]j]
:从前i
个数中**选**,总和正好等于j
,一共有多少种选法
-
推导状态转移方程:根据最后一个位置的情况,分情况讨论
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]
-
初始化:
- 多开一行及一列虚拟结点
- 第一列除
[0, 0]
,其余无需初始化- 这里第一列不会越界访问,可以交给DP阶段处理
- 因为只有
dp[i - 1][j - nums[i]]
可能越界访问- 但是在判定后,只有
j == nums[i] == 0
的情况,才会进入第一列,此时又不会越界 - 如果不符合条件,就不会进来,也不会触发越界访问
- 但是在判定后,只有
-
确定填表顺序:从上往下
-
确定返回值:
dp[n][a]
-
-
滚动数字优化同[模板] 背包
3.代码实现
// v1.0
int findTargetSumWays(vector<int>& nums, int target)
{// 问题转换int sum = 0;for(auto& x : nums){sum += x;}int aim = (sum + target) / 2;// 边界处理if(aim < 0 || (sum + target) % 2) return 0;int n = nums.size();vector<vector<int>> dp(n + 1, vector<int>(aim + 1));dp[0][0] = 1;for(int i = 1; i <= n; i++){for(int j = 0; j <= aim; j++) // 第一列没有初始化,也在DP阶段处理{dp[i][j] = dp[i - 1][j];if(j >= nums[i - 1]){dp[i][j] += dp[i - 1][j - nums[i - 1]];}}}return dp[n][aim];
}
-----------------------------------------------------------------------
// v2.0 滚动数组优化
int findTargetSumWays(vector<int>& nums, int target)
{// 问题转换int sum = 0;for(auto& x : nums){sum += x;}int aim = (sum + target) / 2;// 边界处理if(aim < 0 || (sum + target) % 2) return 0;int n = nums.size();vector<int> dp(aim + 1);dp[0] = 1;for(int i = 1; i <= n; i++){for(int j = aim; j >= nums[i - 1]; j--){dp[j] += dp[j - nums[i - 1]];}}return dp[aim];
}
2.最后一块石头的重量 II
1.题目链接
- 最后一块石头的重量 II
2.算法原理详解
-
问题转化:在数组中选择一些数,让这些数的和尽可能接近
sum / 2
- 问题转化成了目标和–> 01背包
- 问题转化成了目标和–> 01背包
-
思路:
-
确定状态表示 ->
dp[i][j]
的含义dp[i]j]
:从前i
个数中**选**,总和不超过j
,此时的最大和
-
推导状态转移方程:根据最后一个位置的情况,分情况讨论
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
-
初始化:
- 多开一行及一列虚拟结点
- 第一列除
[0, 0]
,其余无需初始化- 这里第一列不会越界访问,可以交给DP阶段处理
- 因为只有
dp[i - 1][j - stones[i - 1]]
可能越界访问- 但是在判定后,只有
j == stones[i - 1] == 0
的情况,才会进入第一列,此时又不会越界 - 如果不符合条件,就不会进来,也不会触发越界访问
- 但是在判定后,只有
-
确定填表顺序:从上往下
-
确定返回值:
sum - 2 * dp[n][sum / 2]
-
-
滚动数字优化同[模板] 背包
3.代码实现
// v1.0
int lastStoneWeightII(vector<int>& stones)
{int sum = 0;for(auto& x : stones){sum += x;}int n = stones.size(), m = sum / 2;vector<vector<int>> dp(n + 1, vector<int>(m + 1));for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){dp[i][j] = dp[i - 1][j];if(j >= stones[i - 1]){dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);}}}return sum - 2 * dp[n][m];
}
-----------------------------------------------------------------------
// v2.0 滚动数组优化
int lastStoneWeightII(vector<int>& stones)
{int sum = 0;for(auto& x : stones){sum += x;}int n = stones.size(), m = sum / 2;vector<int> dp(m + 1);for(int i = 1; i <= n; i++){for(int j = m; j >= stones[i - 1]; j--){dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);}}return sum - 2 * dp[m];
}