本文主要是介绍代码随想录算法训练营第四十二天| 1049. 最后一块石头的重量 II、 494. 目标和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
LeetCode 1049. 最后一块石头的重量 II
题目链接:https://leetcode.cn/problems/last-stone-weight-ii/description/
文章链接:https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
思路
* 最后一块石头的重量:将石头尽量平均分成两堆,即sum/2* 此时就可以计算出装满重量为sum/2的背包最大价值是多少* 那么这个最大价值就是一堆石头的重量,那么另一堆就是sum-最大价值* 两堆石头的重量之差就是最后剩余石头的最小重量
public static int lastStoneWeightII(int[] stones) {int sum = Arrays.stream(stones).sum();int target = sum / 2;int[] dp = new int[target + 1];for (int i = 0; i < stones.length; i++) {for (int 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. 目标和
题目链接:https://leetcode.cn/problems/target-sum/description/
文章链接:https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
思路
* 目标和:若sum为总和,既然为target,那么就一定有 left组合 - right组合 = target* left + right = sum,而sum是固定的。right = sum - left* 公式来了, left - (sum - left) = target 推导出 left = (target + sum)/2* 那么问题转为装满容量为(target + sum)/2有几种装法* dp[j]表示装满背包容量为j的背包有多少种装法,那么对于第i个数,如果不装那依然是dp[j]种装法* 如果装,那就是dp[j-nums[i]]种装法,因此dp[j] = dp[j] + dp[j-nums[i]]
public int findTargetSumWays(int[] nums, int target) {int sum = Arrays.stream(nums).sum();if (Math.abs(target) > sum)return 0;if ((target + sum) % 2 == 1)return 0;int bagSize = (target + sum) / 2;int[] dp = new int[bagSize + 1];dp[0] = 1;for (int i = 0; i < nums.length; i++) {for (int j = bagSize; j >= nums[i] ; j--) {dp[j] = dp[j] + dp[j-nums[i]];}}return dp[bagSize];}
这篇关于代码随想录算法训练营第四十二天| 1049. 最后一块石头的重量 II、 494. 目标和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!