分割等和子集

发表于
本文字数： 3.4k 阅读时长 ≈ 3 分钟

LeetCode每日一题，416. Partition Equal Subset Sum

先看题目描述

题目大意就是给定一个只包含正整数的非空数组，让我们判断是否可以将这个非空数组分割成两个子集

算法和思路

动态规划

一开始看到这题没有头绪，然后去看题解，发现这题可以转化为「0-1 背包问题」使用动态规划解决

算法流程：

  • 状态定义：dp[i][j] 表示从数组的[i, …, len - 1] 区间挑选一些正整数，能否使这些数的和恰好等于 j。能的话 dp[i][j] = true；否则为 false
  • 状态转移方程：很多时候，状态转移方程思考的角度是分类讨论，对于「0-1 背包问题」而言就是「当前考虑到的数字选与不选」
    • 不选择 nums[i] 的话，dp[i][j] = dp[i + 1][j]
    • 选择 nums[i] 的话，dp[i][j] = dp[i + 1][j - nums[i]]
  • 故状态转移方程为 $dp[i][j] = dp[i + 1][j]\quad or \quad dp[i + 1][j - nums[i]]$
  • 考虑初始化条件：
    • j - nums[i] 作为数组下标，故必须保证 $j \geq nums[i]$
    • 虽然 i 的范围是从 0 到 len - 1，但考虑到状态转移方程，要用到下一行的状态，我们定义 dp 数组的行数为 len + 1，并初始化 dp[len][0] = true，用于刚开始的状态转移
  • 返回 dp[0][target]，其中 target 为数组元素之和除 2（若数组元素之和不能被 2 整除，则直接返回 false)

优化

我们之前定义的 dp 数组的行数是 len + 1，列数为 target + 1，但我们观察状态方程，可以发现某一行的状态只与其下一行有关，那么我们没必要维护一个 len + 1 行的 dp 数组，可以只维护一个 2 行的 dp 数组，这样可以节省空间

题解中虽然也是使用的动态规划，但状态的定义不太一样，题解中 dp[i][j] 表示的是从从数组的 [0, …, i] 区间挑选一些正整数，能否使这些数的和恰好等于 j。能的话 dp[i][j] = true；否则为 false，最后返回 dp[len - 1][target] 。两种定义都可以，基本的思路还是一致的

算法源码

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int max = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, nums[i]);
            sum += nums[i];
        }
        if (sum % 2 != 0 || max > sum / 2) {
            return false;
        }
        if (max == sum / 2) {
            return true;
        }
        int target = sum / 2;
        boolean[][] dp = new boolean[len + 1][target + 1];
        for (int i = 0; i <= len; i++) {
            dp[i][0] = true;
        }
        for (int i = len - 1; i > 0; i--) {
            for (int j = 1; j <= target; j++) {
                if (nums[i] > j) {
                    dp[i][j] = dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j] || dp[i + 1][j - nums[i]];
                }
            }
        }
        if (nums[0] > target) {
            dp[0][target] = dp[1][target];
        } else {
            dp[0][target] = dp[1][target - nums[0]];
        }
        return dp[0][target];
    }
}

优化空间后的动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int max = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int num = nums[i];
            max = Math.max(max, num);
            sum += num;
        }
        if (sum % 2 != 0 || max > sum / 2) {
            return false;
        }
        if (max == sum / 2) {
            return true;
        }
        int target = sum / 2;
        boolean[][] dp = new boolean[2][target + 1];
        for (int i = 0; i < 2; i++) {
            dp[i][0] = true;
        }
        for (int i = len - 1; i > 0; i--) {
            int row = i % 2;
            for (int j = 1; j <= target; j++) {
                if (nums[i] > j) {
                    dp[row][j] = dp[1 - row][j];
                } else {
                    dp[row][j] = dp[1 - row][j] || dp[1 - row][j - nums[i]];
                }
            }
        }
        if (nums[0] > target) {
            dp[0][target] = dp[1][target];
        } else {
            dp[0][target] = dp[1][target - nums[0]];
        }
        return dp[0][target];
    }
}