赞
踩
题目:
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。
题解:
动态规划:
创建二维数组 dp \textit{dp} dp,包含 n n n 行 target + 1 \textit{target}+1 target+1列,其中 dp [ i ] [ j ] \textit{dp}[i][j] dp[i][j] 表示从数组的 [ 0 , i ] [0,i] [0,i] 下标范围内选取若干个正整数(可以是 0 个),是否存在一种选取方案使得被选取的正整数的和等于 j j j。初始时, dp \textit{dp} dp 中的全部元素都是 false \text{false} false。
在定义状态之后,需要考虑边界情况。以下两种情况都属于边界情况。
对于 i > 0 i>0 i>0 且 j > 0 j>0 j>0 的情况,如何确定 dp [ i ] [ j ] \textit{dp}[i][j] dp[i][j] 的值?需要分别考虑以下两种情况。
如果 j ≥ nums [ i ] j \ge \textit{nums}[i] j≥nums[i],则对于当前的数字 n u m s [ i ] nums[i] nums[i],可以选取也可以不选取,两种情况只要有一个为 t r u e true true,就有 dp [ i ] [ j ] = true \textit{dp}[i][j]=\text{true} dp[i][j]=true。
如果不选取 nums [ i ] \textit{nums}[i] nums[i],则 dp [ i ] [ j ] = dp [ i − 1 ] [ j ] \textit{dp}[i][j]=\textit{dp}[i-1][j] dp[i][j]=dp[i−1][j];
如果选取 n u m s [ i ] nums[i] nums[i],则 dp [ i ] [ j ] = dp [ i − 1 ] [ j − nums [ i ] ] \textit{dp}[i][j]=\textit{dp}[i-1][j-\textit{nums}[i]] dp[i][j]=dp[i−1][j−nums[i]]。
如果
j
<
nums
[
i
]
j < \textit{nums}[i]
j<nums[i],则在选取的数字的和等于
j
j
j 的情况下无法选取当前的数字
n
u
m
s
[
i
]
nums[i]
nums[i],因此有
dp
[
i
]
[
j
]
=
dp
[
i
−
1
]
[
j
]
\textit{dp}[i][j]=\textit{dp}[i-1][j]
dp[i][j]=dp[i−1][j]。
状态转移方程如下:
dp
[
i
]
[
j
]
=
{
dp
[
i
−
1
]
[
j
]
∣
dp
[
i
−
1
]
[
j
−
nums
[
i
]
]
,
j
≥
nums
[
i
]
dp
[
i
−
1
]
[
j
]
,
j
<
nums
[
i
]
\textit{dp}[i][j]=
最终得到 dp [ n − 1 ] [ target ] \textit{dp}[n-1][\textit{target}] dp[n−1][target]即为答案。
java代码:
public boolean canPartition(int[] nums) { int n = nums.length; if (n < 2) return false; int sum = 0; int maxValue = 0; for (int num : nums) { sum += num; maxValue = Math.max(maxValue, num); } //总和是奇数 if (sum % 2 != 0) { return false; } //最大值超过总和的一半 int target = sum / 2; if (maxValue > target) { return false; } // dp[i][j] : 从[0,i]中选取nums中的若干个正整数使得和为j boolean[][] dp = new boolean[n][target + 1]; for (int i = 0; i < n; i++) { //从[0,i]中不选任何正整数 dp[i][0] = true; } //i=0时,只有一个正数nums[0]可以被选取 dp[0][nums[0]] = true; for (int i = 1; i < n; i++) { int num = nums[i]; for (int j = 1; j <= target; j++) { if (j >= num) { dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num]; } else { dp[i][j] = dp[i - 1][j]; } } } return dp[n - 1][target]; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。