华为云免费服务器,win10优化工具,浙江建设继续教育学院网站,网站建设步骤图片素材一、LeetCode1049. 最后一块石头的重量 II
题目链接#xff1a;1049. 最后一块石头的重量 II
题目描述#xff1a;
有一堆石头#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合#xff0c;从中选出任意两块石头#xff0c;然后将…一、LeetCode1049. 最后一块石头的重量 II
题目链接1049. 最后一块石头的重量 II
题目描述
有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下
如果 x y那么两块石头都会被完全粉碎如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。
最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。 示例 1
输入stones [2,7,4,1,8,1]
输出1
解释
组合 2 和 4得到 2所以数组转化为 [2,7,1,8,1]
组合 7 和 8得到 1所以数组转化为 [2,1,1,1]
组合 2 和 1得到 1所以数组转化为 [1,1,1]
组合 1 和 1得到 0所以数组转化为 [1]这就是最优值。示例 2
输入stones [31,26,33,21,40]
输出5提示
1 stones.length 301 stones[i] 100
算法分析
定义dp数组及下标含义
dp[j]:表示容量为j的背包所能装的物品最大价值石头的重量为dp[j]。
递推公式
dp[j]max(dp[j],dp[j-stones[i]]stones[i])。
初始化
dp[0]0。
遍历顺序
先遍历物品在遍历背包容量。
代码如下
class Solution {public int lastStoneWeightII(int[] stones) {int len stones.length;int sum 0;for(int i 0; i len; i)sum stones[i];int mid;mid sum / 2;int[] dp new int[mid 1];for(int i stones[0]; i mid; i)dp[i] stones[0];for(int i 1; i len; i) {for(int j mid; j stones[i]; j--) {dp[j] Math.max(dp[j], dp[j - stones[i]] stones[i]);}}return sum - dp[mid] * 2;}
}
二、LeetCode494. 目标和
题目链接494. 目标和
题目描述
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 或 - 然后串联起所有整数可以构造一个 表达式
例如nums [2, 1] 可以在 2 之前添加 在 1 之前添加 - 然后串联起来得到表达式 2-1 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 示例 1
输入nums [1,1,1,1,1], target 3
输出5
解释一共有 5 种方法让最终目标和为 3 。
-1 1 1 1 1 3
1 - 1 1 1 1 3
1 1 - 1 1 1 3
1 1 1 - 1 1 3
1 1 1 1 - 1 3示例 2
输入nums [1], target 1
输出1提示
1 nums.length 200 nums[i] 10000 sum(nums[i]) 1000-1000 target 1000
算法分析
设添加的元素集合总和为add添加-的元素集合总和为des则原数组的所有元素之和sumadddes
由题意targetadd-des
desadd-target;
sumadd(add-target);
add(sumtarget)/2;
所以我们只需要在原数组中找出和等于add的方法数就可以了。
于是我们可以用动态规划中背包思路来解。
定义dp数组及下标含义
dp[j]表示元素和为j的方法有dp[j]种。
递推公式
dp[j]dp[j-nums[i]]
例如若有元素123456,则加上该元素后和为5的方法有dp[5]dp[5-1]dp[5-2]dp[5-3]dp[5-4]dp[5-5]种(jnums[i])。
初始化
我们初始化dp[0]1;
表示元素和为0的方法有一种因为如果为0的话那么所有的递推结果都将为0。
遍历顺序
先遍历元素在遍历总和。
代码如下
class Solution {public int findTargetSumWays(int[] nums, int target) {int len nums.length;int sum 0;//数组总和for(int i 0; i len; i)sum nums[i];if(Math.abs(target) sum) return 0;//如果target的绝对值大于sum那么无论数组中所有元素都取正还是负都不肯能等于targetif((sum target) % 2 ! 0) return 0;//没有结果如sum是5target是0的话无解int add (sum target) / 2;int[] dp new int[add 1];dp[0] 1;for(int i 0; i len; i) {for(int j add; j nums[i]; j--) {dp[j] dp[j - nums[i]];}}return dp[add];}
}
总结
求背包问题时要明确定义dp数组所表示的含义对于不同的问题可能会有不同的定义
如1049. 最后一块石头的重量 II中dp[j]表示容量为j的背包所能装的石头的重量最大为dp[j]。
而494. 目标和中dp[j]表示装满容量为j的方法有dp[j]种。
