本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠。在這一系列刷題文章中，我不僅會講解多種解題思路及其優(yōu)化，還會用多種編程語言實現(xiàn)題解，涉及到通用解法時更將歸納總結(jié)出相應(yīng)的算法模板。

為了方便在PC上運行調(diào)試、分享代碼文件，我還建立了相關(guān)的倉庫：https://github.com/memcpy0/LeetCode-Conquest。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結(jié)等，還可以看到原題出現(xiàn)頻率和相關(guān)企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。

由于本系列文章的內(nèi)容隨時可能發(fā)生更新變動，歡迎關(guān)注和收藏征服LeetCode系列文章目錄一文以作備忘。

給你一個長度為?n?的數(shù)組?nums?和一個整數(shù)?m?。請你判斷能否執(zhí)行一系列操作，將數(shù)組拆分成?n?個?非空?數(shù)組。

在每一步操作中，你可以選擇一個?長度至少為 2?的現(xiàn)有數(shù)組（之前步驟的結(jié)果） 并將其拆分成?2?個子數(shù)組，而得到的?每個?子數(shù)組，至少?需要滿足以下條件之一：

• 子數(shù)組的長度為 1 ，或者
• 子數(shù)組元素之和?大于或等于??m?。

如果你可以將給定數(shù)組拆分成?n?個滿足要求的數(shù)組，返回?true?；否則，返回?false?。

注意： 子數(shù)組是數(shù)組中的一個連續(xù)非空元素序列。

示例 1：

輸入：nums = [2, 2, 1], m = 4
輸出：true
解釋：
第 1 步，將數(shù)組 nums 拆分成 [2, 2] 和 [1] 。
第 2 步，將數(shù)組 [2, 2] 拆分成 [2] 和 [2] 。
因此，答案為 true 。

示例 2：

輸入：nums = [2, 1, 3], m = 5 
輸出：false
解釋：
存在兩種不同的拆分方法：
第 1 種，將數(shù)組 nums 拆分成 [2, 1] 和 [3] 。
第 2 種，將數(shù)組 nums 拆分成 [2] 和 [1, 3] 。
然而，這兩種方法都不滿足題意。因此，答案為 false 。

示例 3：

輸入：nums = [2, 3, 3, 2, 3], m = 6
輸出：true
解釋：
第 1 步，將數(shù)組 nums 拆分成 [2, 3, 3, 2] 和 [3] 。
第 2 步，將數(shù)組 [2, 3, 3, 2] 拆分成 [2, 3, 3] 和 [2] 。
第 3 步，將數(shù)組 [2, 3, 3] 拆分成 [2] 和 [3, 3] 。
第 4 步，將數(shù)組 [3, 3] 拆分成 [3] 和 [3] 。
因此，答案為 true 。 

提示：

• 1 <= n == nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= m <= 200

---

解法1 記憶化DFS/區(qū)間DP+前綴和

為了方便求出子數(shù)組的和，我們使用前綴和。

對于數(shù)組拆分，很自然地想到DFS，但如果每次都在數(shù)組兩側(cè)拆分，則復(fù)雜度可能到 $O(2^{100})$ ，為此必須使用記憶化+DFS。我個人的寫法如下所示，令 $dfs(l,r)$ 表示區(qū)間 $[l,r]$ 可否拆分：

• 遞歸邊界：區(qū)間長度 $\le 2$ ，一定可拆分；在區(qū)間長度 $>2$ 且區(qū)間和 $\le m$ 時，此時無論如何都無法繼續(xù)拆分下去。
• 遞歸過程：只有區(qū)間和大于 $m$ 且可以拆分出子區(qū)間 $[l+1,r]$ 或 $[l,r?1]$（對應(yīng)區(qū)間長度為 $1$ 或區(qū)間和 $\ge m$ ），且滿足子區(qū)間可拆分——即 $dfs(l+1,r)=true$ 或 $dfs(l,r?1)=true$ ，此時區(qū)間 $[l,r]$ 可以拆分。

class Solution {
private:int m;int sum[110];int dp[110][110];int dfs(int l, int r) {if (dp[l][r] != -1) return dp[l][r]; // 已經(jīng)有答案if (l + 1 >= r) return dp[l][r] = 1; // 拆分前進行判斷,可以拆分if (sum[r + 1] - sum[l] <= m) return dp[l][r] = 0; // 拆分前進行判斷,不可拆分int left = 0, right = 0;if (l + 1 == r || sum[r + 1] - sum[l + 1] >= m) // 看是否可以拆分出[l+1,r]這個子數(shù)組left = dfs(l + 1, r); // 看[l+1,r]子數(shù)組是否可繼續(xù)拆分if (l == r - 1 || sum[r] - sum[l] >= m) // 看是否可以拆分出[l,r-1]這個子數(shù)組right = dfs(l, r - 1); // 看[l,r-1]子數(shù)組是否可繼續(xù)拆分return dp[l][r] = left || right; }
public:bool canSplitArray(vector<int>& nums, int m) {this->m = m;memset(sum, 0, sizeof(sum));memset(dp, -1, sizeof(dp));int n = nums.size();for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + nums[i];return dfs(0, n - 1);}
};

還可使用區(qū)間DP：

class Solution {
public:bool canSplitArray(vector<int>& nums, int m) {int sum[110];bool dp[110][110];memset(sum, 0, sizeof(sum));memset(dp, false, sizeof(dp));int n = nums.size();for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + nums[i];// dp[i][j]表示區(qū)間[i,j]能否拆分for (int i = n - 1; i >= 0; --i) {dp[i][i] = true;if (i + 1 < n) dp[i][i + 1] = true;// 區(qū)間[i,j-1], [i+1,j]是否可拆for (int j = i + 2; j < n; ++j) {// [i,j]能否拆分為[i+1,j]或[i,j-1],看拆出子數(shù)組的和是否>=m,且拆出子數(shù)組是否可繼續(xù)拆分if (sum[j] - sum[i] >= m && dp[i][j - 1]|| sum[j + 1] - sum[i + 1] >= m && dp[i + 1][j])dp[i][j] = true;        }}return dp[0][n - 1];}
};

---

解法2 腦筋急轉(zhuǎn)彎（最優(yōu)解法）

要善于將題目轉(zhuǎn)換成另外一種解法，對題目的理解、數(shù)學(xué)邏輯要求較高。

• 先特判 $n\le 2$ 的情況，這是滿足要求的。
• 對于 $n\ge 3$ 的情況，無論按照何種方式分割，一定會在某個時刻，分割出一個長為 $2$ 的子數(shù)組。
  • 如果 $\text{nums}$ 中任何長為 $2$ 的子數(shù)組的元素和都小于 $m$ ，那么無法滿足要求。
  • 否則，可以用這個子數(shù)組作為「核心」，像剝洋蔥一樣，一個一個地去掉 $\text{nums}$ 的首尾元素，最后得到這個子數(shù)組。由于子數(shù)組的元素和 $\ge m$ ，所以每次分割出一個元素時，剩余的子數(shù)組的元素和也必然是 $\ge m$ 的，滿足要求。

于是本題可轉(zhuǎn)換成：求數(shù)組中是否存在2個相鄰元素之和 $\ge m$ 。相信題目如果這么問，100%的人都能做出來。

class Solution {
public:bool canSplitArray(vector<int>& nums, int m) {int n = nums.size();for (int i = 1; i < n; ++i)if (nums[i - 1] + nums[i] >= m) return true;return n <= 2;}
};