力扣剑指 Offer II 101. 分割等和子集

最新推荐文章于 2023-01-06 17:10:59 发布

三更鬼

最新推荐文章于 2023-01-06 17:10:59 发布

阅读量223

点赞数

分类专栏：动态规划文章标签： leetcode 算法动态规划

本文链接：https://blog.csdn.net/csdn_muxin/article/details/125221149

版权

动态规划专栏收录该内容

40 篇文章

订阅专栏

该博客讨论了一种算法问题，即判断一个数组是否能被分成两个和相等的子序列。首先检查数组总和是否为偶数，然后利用动态规划的方法，通过二维布尔数组dp来记录前i个元素是否能组成和为j的序列。博客中详细解释了状态转移方程，并展示了如何使用滚动数组优化空间复杂度。最后，通过倒序遍历数组并更新dp数组，当找到能组成目标和的子序列时返回true，否则返回false。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目来源：https://leetcode.cn/problems/NUPfPr/

大致题意：

给定一个数组，求数组能否分成两个和相等的子序列

思路

相当于求数组是否有子序列和可以等于数组和的一半

于是可以先求出数组和，判断数组和是否是偶数，若不是直接返回 false

若是，可以使用动态规划解决

使用二维布尔数组 dp[i][j] 表示数组前 i 个元素是否可以组成和为 j 的序列

那么有

dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]]

初始时，dp[i][0] = true

因为 dp[i] 的值只与 dp[i - 1] 有关，且 dp[i][j] 只与 dp[i - 1][k] （其中 k 小于等于 j）有关，所以可以用滚动数组优化

dp[j] = dp[j] | dp[j - nums[i]

遍历时，需要倒序进行遍历，防止本轮更新的较小位置元素值影响到后面元素值

初始时，dp[0] = true

代码：

public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) {
            return false;
        }
        int n = nums.length;
        int t = sum / 2;
        // 滚动数组
        boolean[] dp = new boolean[t + 1];
        // 初始化
        dp[0] = true;
        for (int num : nums) {
            for (int j = t; j >= num; j--) {
                // 状态转移方程
                dp[j] = dp[j] || dp[j - num];
            }
            // 只要当前子序列可以组成 t，直接返回结果
            if (dp[t]) {
                return true;
            }
        }
        return false;
    }