求人做网站的网站,宣传类的网站,有网站和无网站的区别,做网站去什么公司好目录 1.目标和1.题目链接2.算法原理详解3.代码实现 2.最后一块石头的重量 II1.题目链接2.算法原理详解3.代码实现 1.目标和
1.题目链接
目标和 2.算法原理详解 问题转化#xff1a;在数组中选择一些数#xff0c;让这些数的和等于a#xff0c;一共有多少种选法#xff1f… 目录 1.目标和1.题目链接2.算法原理详解3.代码实现 2.最后一块石头的重量 II1.题目链接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(vectorint 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();vectorvectorint dp(n 1, vectorint(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(vectorint 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();vectorint 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背包 思路 确定状态表示 - 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(vectorint stones)
{int sum 0;for(auto x : stones){sum x;}int n stones.size(), m sum / 2;vectorvectorint dp(n 1, vectorint(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(vectorint stones)
{int sum 0;for(auto x : stones){sum x;}int n stones.size(), m sum / 2;vectorint 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];
}
