问题描述
给定一个整数数组，1 <= nums.length <= 200，1 <= nums[i] <= 100，要求判断是否可以将数组分割成两个子数组，并且这两个子数组的元素和相同。题目链接：点我
样例输入输出
输入：[1,5,11,5]
输出：true
输入：[1,2,3,5]
输出：false
问题解法
此题用暴力求解会超时，需要使用动态规划进行求解，可以将此题转换为从数组中挑选出 k 个元素，使这些元素和等于目标数。此题类似背包问题，用 dp[i][j] 表示前 i 个元素中是否存在某些元素和等于 j，针对每个新元素都存在选与不选的情况，动态转移方程为：dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]] 。代码如下
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) {
int total = Arrays.stream(nums).sum();
if (total % 2 != 0) {
return false;
}
boolean[][] dp = new boolean[nums.length][total + 1];
for (int i = 0; i < nums.length; i++) {
dp[i][nums[i]] = true;
}
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
dp[i][j] = dp[i - 1][j] || (j >= nums[i] && dp[i - 1][j - nums[i]]);
}
}
return dp[nums.length - 1][total / 2];
}
}
|