给你一个长度为 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
方法一：记忆化搜索
我们先预处理得到前缀和数组
接下来，我们设计一个函数 true，否则返回 false。
函数
如果 true；
否则，我们枚举拆分点
- 子数组
$nums[i,..k]$ 只有一个元素，或者子数组$nums[i,..k]$ 的元素之和大于等于$m$ ； - 子数组
$nums[k + 1,..j]$ 只有一个元素，或者子数组$nums[k + 1,..j]$ 的元素之和大于等于$m$ ； -
$dfs(i, k)$ 和$dfs(k + 1, j)$ 都为true。
为了避免重复计算，我们使用记忆化搜索的方法，用一个二维数组
时间复杂度
方法二：脑筋急转弯
不论如何操作，最终总会剩下一个 length == 2 的子数组，又因为元素数值不存在负数，所以随着分割操作的进行，子数组的长度和总和都会逐渐变小，其它 length > 2 子数组之和肯定要比该子数组之和更大，进而，我们只需要考虑，是否存在一个 length == 2 且总和大于等于 m 的子数组即可。
📢 注意，当
nums.length <= 2时，无需进行操作。
时间复杂度
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)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;
}
}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);
}
};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)
}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);
}function canSplitArray(nums: number[], m: number): boolean {
const n = nums.length;
if (n <= 2) {
return true;
}
for (let i = 1; i < n; i++) {
if (nums[i - 1] + nums[i] >= m) {
return true;
}
}
return false;
}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
}
}