濮阳房产网站建设,wordpress新闻动态不显示作者,漂亮的flash网站,简述建设一个网站的过程学习目标#xff1a; 动态规划五部曲#xff1a; ① 确定dp[i]的含义 ② 求递推公式 ③ dp数组如何初始化 ④ 确定遍历顺序 ⑤ 打印递归数组 ---- 调试 引用自代码随想录#xff01; 60天训练营打卡计划#xff01;
学习内容#xff1a;
416.分割等和子集
该题目可以等…学习目标 动态规划五部曲 ① 确定dp[i]的含义 ② 求递推公式 ③ dp数组如何初始化 ④ 确定遍历顺序 ⑤ 打印递归数组 ---- 调试 引用自代码随想录 60天训练营打卡计划
学习内容
416.分割等和子集
该题目可以等效为一个重量和价值相等的01背包问题所以使用一维的数组就可。
因为题目问的是可不可以分为两个等和子集没有问具体应该怎么分。动态规划五步曲 ① 确定dp[j]的含义 容量为j的背包的最大价值 ② 求递推公式 dp[j] max(dp[j], dp[j-nums[i]] nums[i]) ③ dp数组如何初始化 全部为零 ④ 确定遍历顺序 先遍历物品再倒叙遍历背包。实现的特别巧妙将该问题视为一个重量和价值相等的01背包问题将目标和作为背包的重量只要背包重量最大时能达到目标和的价值即找到了一组数满足目标那么此时该数组就可以分为等和的子集。
class Solution {public boolean canPartition(int[] nums) {int total 0;for(int num :nums){total num;}if(total % 2 1) return false;// target就是背包的最大重量int target total / 2;int[] dp new int[target1];// 初始化数组定义的时候已经被全部赋值0// 递推函数for(int i 0; i nums.length; i){for(int j target; j 0; j--){if(j nums[i]) dp[j] dp[j];else{dp[j] Math.max(dp[j], dp[j - nums[i]]nums[i]);}}}// 因为target是整除2得到的所以只要能找到一组数使其和为target// 剩下的数的和也是targetif(dp[target] target) return true;else return false;}
}1049.最后一块石头的重量II
该题目可以等效为一个重量和价值相等的01背包问题所以使用一维的数组就可。
本题中不好理解的点为什么 sum - 2 * dp[target] 就一定是我们要求的结果虽然事实告诉我就是如此。target作为数组重量和的平均值重量和价值相等此时dp[target]的值最大价值一定也小于等于数组重量和的平均值最接近平均值的值。动态规划五步曲 ① 确定dp[j]的含义 容量为j的背包的最大价值 ② 求递推公式 dp[j] max(dp[j], dp[j-stones[i]] stones[i]) ③ dp数组如何初始化 全部为零 ④ 确定遍历顺序 先遍历物品再倒叙遍历背包。
class Solution {public int lastStoneWeightII(int[] stones) {int sum 0;for(int stone:stones){sum stone;}int target sum / 2;int itemSize stones.length;int[] dp new int[target1];// 初始化// 递归函数for(int i 0; i itemSize; i){for(int j target; j 0; j--){if(j stones[i]) dp[j] dp[j];elsedp[j] Math.max(dp[j],dp[j-stones[i]]stones[i]);}// for(int num: dp){// System.out.println(num );// }}return sum - 2 * dp[target];}
}学习时间
上午两个半小时整理文档半小时。
