题目描述
给你一个长度为 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 <= 1001 <= nums[i] <= 1001 <= m <= 200
解法
方法一：记忆化搜索
我们先预处理得到前缀和数组 $s$，其中 $s[i]$ 表示数组 $nums$ 的前 $i$ 个元素之和。
接下来，我们设计一个函数 $dfs(i, j)$，表示对于数组 $nums$ 的下标范围 $[i, j]$，是否存在一种满足条件的拆分方法。如果存在，返回 true，否则返回 false。
函数 $dfs(i, j)$ 的计算过程如下：
如果 $i = j$，那么只有一个元素，不需要拆分，返回 true；
否则，我们枚举拆分点 $k$，其中 $k \in [i, j]$，如果满足以下条件，那么就可以拆分成 $nums[i,.. k]$ 和 $nums[k + 1,.. j]$ 两个子数组：
- 子数组 $nums[i,..k]$ 只有一个元素，或者子数组 $nums[i,..k]$ 的元素之和大于等于 $m$；
- 子数组 $nums[k + 1,..j]$ 只有一个元素，或者子数组 $nums[k + 1,..j]$ 的元素之和大于等于 $m$；
- $dfs(i, k)$ 和 $dfs(k + 1, j)$ 都为
true。
为了避免重复计算，我们使用记忆化搜索的方法，用一个二维数组 $f$ 记录所有的 $dfs(i, j)$ 的返回值，其中 $f[i][j]$ 表示 $dfs(i, j)$ 的返回值。
时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 是数组 $nums$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution:
def canSplitArray(self, nums: List[int], m: int) -> bool:
@cache
def dfs(i: int, j: int) -> bool:
if i == j:
return True
for k in range(i, j):
a = k == i or s[k + 1] - s[i] >= m
b = k == j - 1 or s[j + 1] - s[k + 1] >= m
if a and b and dfs(i, k) and dfs(k + 1, j):
return True
return False
s = list(accumulate(nums, initial=0))
return dfs(0, len(nums) - 1)
|
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 | class Solution {
private Boolean[][] f;
private int[] s;
private int m;
public boolean canSplitArray(List<Integer> nums, int m) {
int n = nums.size();
f = new Boolean[n][n];
s = new int[n + 1];
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums.get(i - 1);
}
this.m = m;
return dfs(0, n - 1);
}
private boolean dfs(int i, int j) {
if (i == j) {
return true;
}
if (f[i][j] != null) {
return f[i][j];
}
for (int k = i; k < j; ++k) {
boolean a = k == i || s[k + 1] - s[i] >= m;
boolean b = k == j - 1 || s[j + 1] - s[k + 1] >= m;
if (a && b && dfs(i, k) && dfs(k + 1, j)) {
return f[i][j] = true;
}
}
return f[i][j] = false;
}
}
|
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 | class Solution {
public:
bool canSplitArray(vector<int>& nums, int m) {
int n = nums.size();
vector<int> s(n + 1);
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
int f[n][n];
memset(f, -1, sizeof f);
function<bool(int, int)> dfs = [&](int i, int j) {
if (i == j) {
return true;
}
if (f[i][j] != -1) {
return f[i][j] == 1;
}
for (int k = i; k < j; ++k) {
bool a = k == i || s[k + 1] - s[i] >= m;
bool b = k == j - 1 || s[j + 1] - s[k + 1] >= m;
if (a && b && dfs(i, k) && dfs(k + 1, j)) {
f[i][j] = 1;
return true;
}
}
f[i][j] = 0;
return false;
};
return dfs(0, n - 1);
}
};
|
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 | func canSplitArray(nums []int, m int) bool {
n := len(nums)
f := make([][]int, n)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
for i := range f {
f[i] = make([]int, n)
}
var dfs func(i, j int) bool
dfs = func(i, j int) bool {
if i == j {
return true
}
if f[i][j] != 0 {
return f[i][j] == 1
}
for k := i; k < j; k++ {
a := k == i || s[k+1]-s[i] >= m
b := k == j-1 || s[j+1]-s[k+1] >= m
if a && b && dfs(i, k) && dfs(k+1, j) {
f[i][j] = 1
return true
}
}
f[i][j] = -1
return false
}
return dfs(0, n-1)
}
|
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 | function canSplitArray(nums: number[], m: number): boolean {
const n = nums.length;
const s: number[] = new Array(n + 1).fill(0);
for (let i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
const f: number[][] = Array(n)
.fill(0)
.map(() => Array(n).fill(-1));
const dfs = (i: number, j: number): boolean => {
if (i === j) {
return true;
}
if (f[i][j] !== -1) {
return f[i][j] === 1;
}
for (let k = i; k < j; ++k) {
const a = k === i || s[k + 1] - s[i] >= m;
const b = k === j - 1 || s[j + 1] - s[k + 1] >= m;
if (a && b && dfs(i, k) && dfs(k + 1, j)) {
f[i][j] = 1;
return true;
}
}
f[i][j] = 0;
return false;
};
return dfs(0, n - 1);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | impl Solution {
pub fn can_split_array(nums: Vec<i32>, m: i32) -> bool {
let n = nums.len();
if n <= 2 {
return true;
}
for i in 1..n {
if nums[i - 1] + nums[i] >= m {
return true;
}
}
false
}
}
|
方法二：脑筋急转弯
不论如何操作，最终总会剩下一个 length == 2 的子数组，又因为元素数值不存在负数，所以随着分割操作的进行，子数组的长度和总和都会逐渐变小，其它 length > 2 子数组之和肯定要比该子数组之和更大，进而，我们只需要考虑，是否存在一个 length == 2 且总和大于等于 m 的子数组即可。
📢 注意，当 nums.length <= 2 时，无需进行操作。
时间复杂度 $O(n)$，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$。