赞
踩
问题转化:在数组中选择一些数,让这些数的和等于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[i - 1][j - nums[i]]
可能越界访问
j == nums[i] == 0
的情况,才会进入第一列,此时又不会越界确定填表顺序:从上往下
确定返回值:dp[n][a]
滚动数字优化同[模板] 背包
// 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]; }
问题转化:在数组中选择一些数,让这些数的和尽可能接近sum / 2
思路:
确定状态表示 -> 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[i - 1][j - stones[i - 1]]
可能越界访问
j == stones[i - 1] == 0
的情况,才会进入第一列,此时又不会越界确定填表顺序:从上往下
确定返回值:sum - 2 * dp[n][sum / 2]
滚动数字优化同[模板] 背包
// 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]; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。