分割等和子串

题目链接(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

  1. 确定dp公式

我们要求的是dp[j] 也就是容量为 j 的背包的最大重量

那么也就是对于每一个 dp[j] 我们都要比较大小 ，然后返回最大的即可

本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。

dp[j] = Math.max(dp[j] , dp[j - nums[i]] + nums[i])

  1. dp的初始化 及大小

对于dp数组而言 ， 它的初始化 是根据题意来进行写的， 我们这里就是初始化为 0

dp数组的大小 也就是背包的所能承受的最大重量

容量 ： 给定的数组中的所有元素之和 / 2得到的结果 + 1 就是最大容量‘【加一是因为整除他会向下取整】

容量最大值 ： 【注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200】 那么就是 （100 * 200 ）/2

  1. 遍历顺序

同样的 和背包问题一样， 我们这里需要两层遍历

第一层遍历数值

第二层遍历背包 

1
2
3
4
5
6
// 开始 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数组的最大重量是否等于背包的最大重量

所以需要进行判断

1
2
3
4
if(dp[target] == target)
    return true;
else
    return false;

整体代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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]

换位思考到本题即可

  1. 确定dp数组公式

dp[j] = Math.max(dp[j] , dp[j - nums[i]] + nums[i])

  1. dp数组的初始化

这里我们全部初始化为0 即可

大小 ：也就是数组中的所有元素之和 / 2得到的结果 + 1 就是最大容量【加一是因为整除他会向下取整】

  1. 确定遍历顺序

和前面的题一样。 如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历

最后返回

相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target] —> sum - 2 * dp[target]

整体代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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];
    }
}