本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠(yuǎn)。在這一系列刷題文章中，我不僅會(huì)講解多種解題思路及其優(yōu)化，還會(huì)用多種編程語言實(shí)現(xiàn)題解，涉及到通用解法時(shí)更將歸納總結(jié)出相應(yīng)的算法模板。
為了方便在PC上運(yùn)行調(diào)試、分享代碼文件，我還建立了相關(guān)的倉庫：https://github.com/memcpy0/LeetCode-Conquest。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結(jié)等，還可以看到原題出現(xiàn)頻率和相關(guān)企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。
由于本系列文章的內(nèi)容隨時(shí)可能發(fā)生更新變動(dòng)，歡迎關(guān)注和收藏征服LeetCode系列文章目錄一文以作備忘。
給你一個(gè)長度為?n?的數(shù)組?nums?和一個(gè)整數(shù)?m?。請你判斷能否執(zhí)行一系列操作，將數(shù)組拆分成?n?個(gè)?非空?數(shù)組。
在每一步操作中，你可以選擇一個(gè)?長度至少為 2?的現(xiàn)有數(shù)組（之前步驟的結(jié)果） 并將其拆分成?2?個(gè)子數(shù)組，而得到的?每個(gè)?子數(shù)組，至少?需要滿足以下條件之一：
- 子數(shù)組的長度為 1 ，或者
- 子數(shù)組元素之和?大于或等于??
m?。
如果你可以將給定數(shù)組拆分成?n?個(gè)滿足要求的數(shù)組，返回?true?；否則，返回?false?。
注意： 子數(shù)組是數(shù)組中的一個(gè)連續(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 <= 1001 <= nums[i] <= 1001 <= m <= 200
解法1 記憶化DFS/區(qū)間DP+前綴和
為了方便求出子數(shù)組的和，我們使用前綴和。
對(duì)于數(shù)組拆分，很自然地想到DFS，但如果每次都在數(shù)組兩側(cè)拆分，則復(fù)雜度可能到 O ( 2 100 ) O(2^{100}) O(2100) ，為此必須使用記憶化+DFS。我個(gè)人的寫法如下所示，令 d f s ( l , r ) dfs(l, r) dfs(l,r) 表示區(qū)間 [ l , r ] [l,r] [l,r] 可否拆分：
- 遞歸邊界：區(qū)間長度 ≤ 2 \le 2 ≤2 ，一定可拆分；在區(qū)間長度 > 2 > 2 >2 且區(qū)間和 ≤ m \le m ≤m 時(shí)，此時(shí)無論如何都無法繼續(xù)拆分下去。
- 遞歸過程：只有區(qū)間和大于 m m m 且可以拆分出子區(qū)間 [ l + 1 , r ] [l + 1, r] [l+1,r] 或 [ l , r ? 1 ] [l, r - 1] [l,r?1]（對(duì)應(yīng)區(qū)間長度為 1 1 1 或區(qū)間和 ≥ m \ge m ≥m ），且滿足子區(qū)間可拆分——即 d f s ( l + 1 , r ) = t r u e dfs(l + 1, r) = true dfs(l+1,r)=true 或 d f s ( l , r ? 1 ) = t r u e dfs(l, r - 1)= true dfs(l,r?1)=true ，此時(shí)區(qū)間 [ l , r ] [l, r] [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; // 拆分前進(jìn)行判斷,可以拆分
if (sum[r + 1] - sum[l] <= m) return dp[l][r] = 0; // 拆分前進(jìn)行判斷,不可拆分
int left = 0, right = 0;
if (l + 1 == r || sum[r + 1] - sum[l + 1] >= m) // 看是否可以拆分出[l+1,r]這個(gè)子數(shù)組
left = dfs(l + 1, r); // 看[l+1,r]子數(shù)組是否可繼續(xù)拆分
if (l == r - 1 || sum[r] - sum[l] >= m) // 看是否可以拆分出[l,r-1]這個(gè)子數(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)換成另外一種解法，對(duì)題目的理解、數(shù)學(xué)邏輯要求較高。文章來源：http://www.zghlxwxcb.cn/news/detail-644765.html
- 先特判 n ≤ 2 n \le 2 n≤2 的情況，這是滿足要求的。
- 對(duì)于
n
≥
3
n\ge 3
n≥3 的情況，無論按照何種方式分割，一定會(huì)在某個(gè)時(shí)刻，分割出一個(gè)長為
2
2
2 的子數(shù)組。
- 如果 nums \textit{nums} nums 中任何長為 2 2 2 的子數(shù)組的元素和都小于 m m m ，那么無法滿足要求。
- 否則，可以用這個(gè)子數(shù)組作為「核心」，像剝洋蔥一樣，一個(gè)一個(gè)地去掉 nums \textit{nums} nums 的首尾元素，最后得到這個(gè)子數(shù)組。由于子數(shù)組的元素和 ≥ m \ge m ≥m ，所以每次分割出一個(gè)元素時(shí)，剩余的子數(shù)組的元素和也必然是 ≥ m \ge m ≥m 的，滿足要求。
于是本題可轉(zhuǎn)換成：求數(shù)組中是否存在2個(gè)相鄰元素之和 ≥ m \ge m ≥m 。相信題目如果這么問，100%的人都能做出來。文章來源地址http://www.zghlxwxcb.cn/news/detail-644765.html
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;
}
};
到了這里，關(guān)于LeetCode 2811. Check if it is Possible to Split Array【腦筋急轉(zhuǎn)彎；前綴和+動(dòng)態(tài)規(guī)劃或記憶化DFS】中等的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
