【力扣357次周赛】6953. 判断是否能拆分数组
给你一个长度为 n
的数组 nums
和一个整数 m
。请你判断能否执行一系列操作,将数组拆分成 n
个 非空 数组。
在每一步操作中,你可以选择一个 长度至少为 2 的现有数组(之前步骤的结果) 并将其拆分成 2 个子数组,而得到的 每个 子数组,至少 需要满足以下条件之一:
- 子数组的长度为 1 ,或者
- 子数组元素之和 大于或等于
m
。
如果你可以将给定数组拆分成 n
个满足要求的数组,返回 true
;否则,返回 false
。
注意:子数组是数组中的一个连续非空元素序列。
示例 1:
输入:nums = [2, 2, 1], m = 4
输出:true
解释:
第 1 步,将数组 nums 拆分成 [2, 2] 和 [1] 。
第 2 步,将数组 [2, 2] 拆分成 [2] 和 [2] 。
因此,答案为 true 。
示例 2:
输入:nums = [2, 1, 3], m = 5
输出:false
解释:
存在两种不同的拆分方法:
第 1 种,将数组 nums 拆分成 [2, 1] 和 [3] 。
第 2 种,将数组 nums 拆分成 [2] 和 [1, 3] 。
然而,这两种方法都不满足题意。因此,答案为 false 。
示例 3:
输入:nums = [2, 3, 3, 2, 3], m = 6
输出:true
解释:
第 1 步,将数组 nums 拆分成 [2, 3, 3, 2] 和 [3] 。
第 2 步,将数组 [2, 3, 3, 2] 拆分成 [2, 3, 3] 和 [2] 。
第 3 步,将数组 [2, 3, 3] 拆分成 [2] 和 [3, 3] 。
第 4 步,将数组 [3, 3] 拆分成 [3] 和 [3] 。
因此,答案为 true 。
提示:
1 <= n == nums.length <= 100
1 <= nums[i] <= 100
1 <= m <= 200
暴力超时
class Solution {
int n;
List<Integer> nums;
int m;
public boolean dfs(int start, int end, int sum) {
if(start + 1 >= end) {
return true;
}
boolean a = false;
if(sum - nums.get(start) >= m) {
a = dfs(start + 1, end, sum - nums.get(start));
}
boolean b = false;
if(sum - nums.get(end) >= m) {
b = dfs(start, end - 1, sum - nums.get(end));
}
return a || b;
}
public boolean canSplitArray(List<Integer> nums, int m) {
this.n = nums.size();
this.nums = nums;
this.m = m;
int sum = 0;
for (int num : nums) {
sum += num;
}
return dfs(0, n-1, sum);
}
}
动态规划
- 赶在最后五分钟做出来的,还是太弱了
- dp方程:dp[i][j] = (dp[i+1][j] && sum(i+1, j) > m) || (dp[i][j-1] && sum(i, j-1) > m)
class Solution {
public boolean canSplitArray(List<Integer> nums, int m) {
int n = nums.size();
boolean[][] dp = new boolean[n][n];
int[] left = new int[n];
for(int i = 0; i < n; i++) {
dp[i][i] = true;
if(i + 1 < n) {
dp[i][i+1] = true;
}
if(i == 0) {
left[i] = nums.get(i);
} else {
left[i] = left[i-1] + nums.get(i);
}
}
for(int i = n; i >= 0; i--) {
for(int j = i + 2; j < n; j++) {
int sum = left[j];
if(i > 0) {
sum -= left[i-1];
}
dp[i][j] = (i + 1 < n && dp[i+1][j] && sum - nums.get(i) >= m)
|| (dp[i][j-1] && sum - nums.get(j) >= m);
}
}
return dp[0][n-1];
}
}
标签:周赛,nums,int,sum,get,357,力扣,数组,dp
From: https://www.cnblogs.com/tod4/p/17609266.html