分割等和子串
题目链接(opens new window)
题目难易：中等
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
示例 1:
- 输入: [1, 5, 11, 5]
- 输出: true
- 解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
- 输入: [1, 2, 3, 5]
- 输出: false
- 解释: 数组不能分割成两个元素和相等的子集.
提示：
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
思路
对于这种类型的题 我们一上来首先想到的肯定不是动归 ，而使回溯，回溯解决切割问题。但是这道题相对于也是可以使用dp去解决的
这道题 他求解的是是否可以分割成两个相等的子集 ，既然想要相同， 那么想要相同，那sum肯定不能是基数 ，如果是奇数 那么就不可能平分 ，所以我们可以先进行判断 ，排除一些不可能的结果。
动归五部曲
1.确定dp数组 含义 以及下标的含义
首先对比背包问题使用dp的的方法
- 背包问题 ： dp[j] ： 表示 背包容量为 j 的背包 所能存放的物品的最大价值是dp[j]
所以说对于本体来讲 ，我们使用的是 数值 那么它的重量 和 价值是相同的
- 本体dp : dp[j] : 表示 背包容量为 j 的背包 ，所能容纳的最大重量为dp[j]
我们所求的最大重量 : 就是 子集中的元素相加最大
容量 ： 给定的数组中的所有元素之和 / 2得到的结果 + 1 就是最大容量‘【加一是因为整除他会向下取整】
容量最大值 ： 【注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200】 那么就是 （100 * 200 ）/2
2.确定dp公式
我们要求的是dp[j] 也就是容量为 j 的背包的最大重量
那么也就是对于每一个 dp[j] 我们都要比较大小 ，然后返回最大的即可
本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。
dp[j] = Math.max(dp[j] , dp[j - nums[i]] + nums[i])
3.dp的初始化 及大小
对于dp数组而言 ， 它的初始化 是根据题意来进行写的， 我们这里就是初始化为 0
dp数组的大小 也就是背包的所能承受的最大重量
容量 ： 给定的数组中的所有元素之和 / 2得到的结果 + 1 就是最大容量‘【加一是因为整除他会向下取整】
容量最大值 ： 【注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200】 那么就是 （100 * 200 ）/2
4.遍历顺序
同样的 和背包问题一样， 我们这里需要两层遍历
第一层遍历数值
第二层遍历背包
// 开始 01背包 for(int i = 0; i < nums.length; i++) { for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历 dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]); } }
最后
我们不能只简单的实现dp数组 ，根据题目要求 ，我们需要判断 该数组能否完成分割 ，也就是dp数组的最大重量是否等于背包的最大重量
所以需要进行判断
if(dp[target] == target) return true; else return false;
整体代码实现
class Solution { public boolean canPartition(int[] nums) { if(nums == null || nums.length == 0) return false; int n = nums.length; int sum = 0; for(int num : nums) { sum += num; } //总和为奇数，不能平分 if(sum % 2 != 0) return false; int target = sum / 2; int[] dp = new int[target + 1]; for(int i = 0; i < n; i++) { for(int j = target; j >= nums[i]; j--) { //物品 i 的重量是 nums[i]，其价值也是 nums[i] dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]); } } return dp[target] == target; } }
最后一块石头的重量
题目链接(opens new window)
题目难度：中等
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
示例：
- 输入：[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]，这就是最优值。
提示：
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 1000
思路
本题的目的是让我们找到碰撞之后 ，重量最小的石头的重量。 同样的 ， 我们可以将其换位思考变化为背包问题
关键点:
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
碰撞之后的重量最小的石头 ，那么就相当于 将两个大小相似的石头进行碰撞 ，到最后剩下的 那么一定是重量最小的石头 ，因为我们找的是重量相近的两个石头碰撞
那么问题的关键就是怎么寻找重量相近的石头 ，答案很简单
先对数组进行求和sum ，然后将 sum/ 2 ，得到一个结果target ，那么另一个值就是 (sum - sum/2) —>（sum -target）
那么我们所需要的最小值就一定是 target - (sum - target) 的绝对值 ，为什么取绝对值 ? 因为我们不知道 target 和 sum-target到底哪个大
动归五部曲
1.确定dp数组及其含义
就刚刚我们的思路而言 ，本题的思路 和 实现 上一题 基本上是如出一辙 。
dp[j] 表示 ： 容量为 j 的背包 ，放置的物品的最大重量为dp[j]
换位思考到本题即可
2.确定dp数组公式
dp[j] = Math.max(dp[j] , dp[j - nums[i]] + nums[i])
3.dp数组的初始化
这里我们全部初始化为0 即可
大小 ：也就是数组中的所有元素之和 / 2得到的结果 + 1 就是最大容量【加一是因为整除他会向下取整】
4.确定遍历顺序
和前面的题一样。 如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历
最后返回
相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target] —> sum - 2 * dp[target]
整体代码实现
class Solution { public int lastStoneWeightII(int[] stones) { int sum = 0; for (int i : stones) { sum += i; } int target = sum >> 1; //初始化dp数组 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 - 2 * dp[target]; } }
