给你一个长度为 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

脑筋急转弯by灵神

  • 先特判 的情况，这是满足要求的。
  • 对于 的情况，无论按照何种方式分割，一定会在某个时刻，分割出一个长为 2 的子数组。
  • 如果 中任何长为 2 的子数组的元素和都小于 m，那么无法满足要求。
  • 否则，可以用这个子数组作为「核心」，像剥洋葱一样，一个一个地去掉 的首尾元素，最后得到这个子数组。由于子数组的元素和 ，所以每次分割出一个元素时，剩余的子数组的元素和也必然是 的，满足要求。
  • 所以问题变成：判断数组中是否有两个相邻数字 。

复杂度

  • 时间复杂度：，其中 为 的长度。
  • 空间复杂度：。仅用到若干额外变量。
    1
    2
    3
    4
    class Solution:
        def canSplitArray(self, nums: List[int], m: int) -> bool:
            n = len(nums)
            return n <= 2 or any(x+y >= m for x,y in pairwise(nums))

区间dp

参考@汪乐平写法

  • 1、获取列表nums的长度，并初始化一个变量来保存长度
  • 2、初始化两个二维布尔数组和，大小都为n x n
  • 3、初始化一个大小为n+1的列表，用于保存的前缀和
  • 4、计算的前缀和，将结果保存在列表s中
  • 5、使用两层循环遍历i和j，计算的值，表示的和是否大于等于m
  • 6、使用三层循环遍历i、j和k，计算的值，表示是否可以将划分为m个非空子数组，且每个子数组的和都大于等于m
  • 7、返回的值，表示是否可以将整个划分为m个非空子数组，且每个子数组的和都大于等于m
  • 8、表示的和是否大于等于m或者长度为1 = 只记录子数组的和
  • 9、表示是否可以将划分为m个非空子数组，且每个子数组的和都大于等于m
  • 10、外层循环是否可以正向遍历呢？
    在第8步中，外层循环使用了逆向遍历，从n-1到0。这是因为在计算时，需要依赖和的值，其中k的范围是i到j-1。所以需要先计算出和，然后才能计算。
  • 11、如果我们使用正向遍历，从0到n-1，那么在计算时，和的值可能还没有被计算出来，导致计算时出现错误的结果。
  • 12、所以，为了保证计算时能够使用正确的和的值，需要使用逆向遍历，即从n-1到0。这样可以确保在计算时，和的值都已经被计算出来了。

状态转移方程

复杂度

  • 时间复杂度：，其中 为 的长度。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution:
        def canSplitArray(self, nums: List[int], m: int) -> bool:
            n = len(nums)
            f = [[False]*n for _ in range(n)]
            b = [[False]*n for _ in range(n)]
            s = [0]*(n+1)
            for i,x in enumerate(nums):
                s[i+1] = s[i] + nums[i]
            for i in range(n):
                for j in range(i,n):
                    b[i][j] = (i==j) or ((s[j+1] - s[i]) >= m)
            for i in range(n-1,-1,-1):
                f[i][i] = True
                for j in range(i+1,n):
                    for k in range(i,j):
                        f[i][j] = f[i][j] or (f[i][k] and f[k+1][j] and b[i][k] and b[k+1][j])
            return f[0][n-1]
    例子：
    输入：nums = [2, 1, 3,4,5], m = 5

    模拟数组初始化的顺序，非真实value