LeetCode 2369 Check if There is a Valid Partition For The Array递归与动态规划四种解法精解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以 LeetCode 2369 题Check if There is a Valid Partition For The Array为核心系统讲解如何判断一个数组能否被分割为若干符合规则的子数组。文章完整继承 check-if-there-is-a-valid-partition-for-the-array.md 中的递归、自顶向下 DP、自底向上 DP、空间优化 DP 四种解法及其多语言实现并结合本仓库 kotlin/2369-check-if-there-is-a-valid-partition-for-the-array.kt 中的实际源码进行印证。读完本文你将掌握这类前缀可行性判断型动态规划问题的完整解题套路、三种递推方向的取舍以及常见边界错误的规避方法。问题定义与前置知识给定一个长度为n的整数数组nums需要判断它能否被分割成一个或多个连续子数组使得每个子数组满足以下三种合法形态之一恰好包含2 个相等的元素例如[2, 2]恰好包含3 个相等的元素例如[4, 4, 4]恰好包含3 个连续递增的元素例如[3, 4, 5]即每个相邻元素相差 1。注意这三种形态是互斥且穷尽的每个子数组的长度只能是 2 或 3且必须严格满足上述某一条规则。在动手写代码之前原文档建议先掌握以下三项基础能力递归Recursion将大问题拆解为带基线条件的小子问题动态规划Dynamic Programming使用记忆化memoization或填表tabulation避免重复计算数组遍历Array Traversal迭代数组并检查元素之间的相邻关系。解法一递归Recursion直觉Intuition核心思路非常直接从数组头部开始每一步只面临两种切分选择——取 2 个元素或取 3 个元素。如果当前位置取 2 个元素能构成合法子数组就递归检查剩余部分如果取 3 个元素能构成合法子数组也递归检查剩余部分。只要任意一条递归路径能把数组走完就说明存在合法分割。这种当前位置只关心下一步取多长的思路是许多区间分割类问题的通用起点。算法步骤定义从索引0开始的递归函数基线条件若i len(nums)说明整个数组已被完整消费返回true当前位置尝试两种选择若nums[i] nums[i1]后两个元素相等则从i2递归若后三个元素全部相等或连续递增则从i3递归只要任意一条递归路径返回true当前位置即返回true所有路径都失败则返回false。多语言实现class Solution: def validPartition(self, nums: List[int]) - bool: def dfs(i): if i len(nums): return True res False if i len(nums) - 1 and nums[i] nums[i 1]: res dfs(i 2) if i len(nums) - 2: if ((nums[i] nums[i 1] nums[i 2]) or (nums[i] 1 nums[i 1] and nums[i 1] 1 nums[i 2]) ): res res or dfs(i 3) return res return dfs(0)public class Solution { public boolean validPartition(int[] nums) { return dfs(nums, 0); } private boolean dfs(int[] nums, int i) { if (i nums.length) return true; boolean res false; if (i nums.length - 1 nums[i] nums[i 1]) { res dfs(nums, i 2); } if (i nums.length - 2) { if ((nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2])) { res res || dfs(nums, i 3); } } return res; } }class Solution { public: bool validPartition(vectorint nums) { return dfs(nums, 0); } private: bool dfs(vectorint nums, int i) { if (i nums.size()) return true; bool res false; if (i nums.size() - 1 nums[i] nums[i 1]) { res dfs(nums, i 2); } if (i nums.size() - 2) { if ((nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2])) { res res || dfs(nums, i 3); } } return res; } };class Solution { /** * param {number[]} nums * return {boolean} */ validPartition(nums) { const dfs (i) { if (i nums.length) return true; let res false; if (i nums.length - 1 nums[i] nums[i 1]) { res dfs(i 2); } if (i nums.length - 2) { if ( (nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2]) ) { res res || dfs(i 3); } } return res; }; return dfs(0); } }public class Solution { public bool ValidPartition(int[] nums) { return Dfs(nums, 0); } private bool Dfs(int[] nums, int i) { if (i nums.Length) return true; bool res false; if (i nums.Length - 1 nums[i] nums[i 1]) { res Dfs(nums, i 2); } if (i nums.Length - 2) { if ((nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2])) { res res || Dfs(nums, i 3); } } return res; } }func validPartition(nums []int) bool { var dfs func(i int) bool dfs func(i int) bool { if i len(nums) { return true } res : false if i len(nums)-1 nums[i] nums[i1] { res dfs(i 2) } if i len(nums)-2 { if (nums[i] nums[i1] nums[i1] nums[i2]) || (nums[i]1 nums[i1] nums[i1]1 nums[i2]) { res res || dfs(i3) } } return res } return dfs(0) }class Solution { fun validPartition(nums: IntArray): Boolean { fun dfs(i: Int): Boolean { if (i nums.size) return true var res false if (i nums.size - 1 nums[i] nums[i 1]) { res dfs(i 2) } if (i nums.size - 2) { if ((nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2])) { res res || dfs(i 3) } } return res } return dfs(0) } }class Solution { func validPartition(_ nums: [Int]) - Bool { func dfs(_ i: Int) - Bool { if i nums.count { return true } var res false if i nums.count - 1 nums[i] nums[i 1] { res dfs(i 2) } if i nums.count - 2 { if (nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2]) { res res || dfs(i 3) } } return res } return dfs(0) } }impl Solution { pub fn valid_partition(nums: Veci32) - bool { fn dfs(nums: [i32], i: usize) - bool { if i nums.len() { return true; } let mut res false; if i nums.len() - 1 nums[i] nums[i 1] { res dfs(nums, i 2); } if i nums.len() - 2 { if (nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2]) { res res || dfs(nums, i 3); } } res } dfs(nums, 0) } }复杂度分析时间复杂度$O(2^n)$。每个位置最多有两个分支取 2 或取 3在最坏情况下递归树按指数规模展开空间复杂度$O(n)$。来自递归调用栈的深度最坏情况是每次只取 2 个元素递归深度为n/2。解法二动态规划自顶向下 / Top-Down直觉Intuition观察递归解法会发现明显的重叠子问题从不同切分路径出发可能反复到达同一个索引i。例如[1,1,1,1]既可以先取 2 再取 2也可以先取 3 再取 1不合法但无论哪条路径一旦到达索引2剩余部分的判定结果都是一样的。用记忆化缓存从索引i出发是否存在合法分割的结果即可把指数级递归压缩为线性。这正是动态规划以空间换时间的典型体现。算法步骤建立记忆化表memo map以起始索引为键存储结果递归函数先查表若当前索引的结果已计算过直接返回基线条件到达数组末尾返回true尝试构成长度为2的合法子数组两元素相等并递归尝试构成长度为3的合法子数组三相等或三连续递增并递归返回前将结果写入 memo最终返回索引0的结果。多语言实现class Solution: def validPartition(self, nums: List[int]) - bool: dp { len(nums) : True } def dfs(i): if i in dp: return dp[i] res False if i len(nums) - 1 and nums[i] nums[i 1]: res dfs(i 2) if i len(nums) - 2: if ((nums[i] nums[i 1] nums[i 2]) or (nums[i] 1 nums[i 1] and nums[i 1] 1 nums[i 2]) ): res res or dfs(i 3) dp[i] res return res return dfs(0)public class Solution { private MapInteger, Boolean memo new HashMap(); public boolean validPartition(int[] nums) { return dfs(nums, 0); } private boolean dfs(int[] nums, int i) { if (i nums.length) return true; if (memo.containsKey(i)) return memo.get(i); boolean res false; if (i nums.length - 1 nums[i] nums[i 1]) { res dfs(nums, i 2); } if (i nums.length - 2) { if ((nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2])) { res res || dfs(nums, i 3); } } memo.put(i, res); return res; } }class Solution { public: unordered_mapint, bool memo; bool validPartition(vectorint nums) { return dfs(nums, 0); } private: bool dfs(vectorint nums, int i) { if (i nums.size()) return true; if (memo.count(i)) return memo[i]; bool res false; if (i nums.size() - 1 nums[i] nums[i 1]) { res dfs(nums, i 2); } if (i nums.size() - 2) { if ((nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2])) { res res || dfs(nums, i 3); } } return memo[i] res; } };class Solution { /** * param {number[]} nums * return {boolean} */ validPartition(nums) { const memo new Map(); const dfs (i) { if (i nums.length) return true; if (memo.has(i)) return memo.get(i); let res false; if (i nums.length - 1 nums[i] nums[i 1]) { res dfs(i 2); } if (i nums.length - 2) { if ( (nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2]) ) { res res || dfs(i 3); } } memo.set(i, res); return res; }; return dfs(0); } }public class Solution { private Dictionaryint, bool memo new Dictionaryint, bool(); public bool ValidPartition(int[] nums) { return Dfs(nums, 0); } private bool Dfs(int[] nums, int i) { if (i nums.Length) return true; if (memo.ContainsKey(i)) return memo[i]; bool res false; if (i nums.Length - 1 nums[i] nums[i 1]) { res Dfs(nums, i 2); } if (i nums.Length - 2) { if ((nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2])) { res res || Dfs(nums, i 3); } } memo[i] res; return res; } }func validPartition(nums []int) bool { memo : make(map[int]bool) var dfs func(i int) bool dfs func(i int) bool { if i len(nums) { return true } if val, ok : memo[i]; ok { return val } res : false if i len(nums)-1 nums[i] nums[i1] { res dfs(i 2) } if i len(nums)-2 { if (nums[i] nums[i1] nums[i1] nums[i2]) || (nums[i]1 nums[i1] nums[i1]1 nums[i2]) { res res || dfs(i3) } } memo[i] res return res } return dfs(0) }class Solution { private val memo HashMapInt, Boolean() fun validPartition(nums: IntArray): Boolean { return dfs(nums, 0) } private fun dfs(nums: IntArray, i: Int): Boolean { if (i nums.size) return true memo[i]?.let { return it } var res false if (i nums.size - 1 nums[i] nums[i 1]) { res dfs(nums, i 2) } if (i nums.size - 2) { if ((nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2])) { res res || dfs(nums, i 3) } } memo[i] res return res } }class Solution { func validPartition(_ nums: [Int]) - Bool { var memo [Int: Bool]() func dfs(_ i: Int) - Bool { if i nums.count { return true } if let val memo[i] { return val } var res false if i nums.count - 1 nums[i] nums[i 1] { res dfs(i 2) } if i nums.count - 2 { if (nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2]) { res res || dfs(i 3) } } memo[i] res return res } return dfs(0) } }impl Solution { pub fn valid_partition(nums: Veci32) - bool { let mut memo vec![-1i8; nums.len() 1]; fn dfs(nums: [i32], i: usize, memo: mut Veci8) - bool { if i nums.len() { return true; } if memo[i] ! -1 { return memo[i] 1; } let mut res false; if i nums.len() - 1 nums[i] nums[i 1] { res dfs(nums, i 2, memo); } if i nums.len() - 2 { if (nums[i] nums[i 1] nums[i 1] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] 1 nums[i 2]) { res res || dfs(nums, i 3, memo); } } memo[i] if res { 1 } else { 0 }; res } dfs(nums, 0, mut memo) } }复杂度分析时间复杂度$O(n)$。每个索引最多被计算一次每次计算仅检查常数个相邻元素空间复杂度$O(n)$。记忆化表最多存储n个键加上递归栈深度。解法三动态规划自底向上 / Bottom-Up直觉Intuition自顶向下是从头递归、向后记忆自底向上则反过来从地基往上盖。定义dp[i]表示前i个元素能否被合法分割然后从小到大填充只要前缀i-2或i-3可合法分割且紧接的 2 个或 3 个元素构成合法子数组前缀i就可合法分割。最终dp[n]就是整个数组的答案。这一思路与原文档给出的递推定义完全一致也是仓库中 Kotlin 实现的dp O(n) space版本所采用的做法见 kotlin/2369-check-if-there-is-a-valid-partition-for-the-array.kt。算法步骤创建大小为n1的 DP 数组初始化为false令dp[0] true空前缀视为合法从i 2迭代到n若nums[i-1] nums[i-2]且dp[i-2]为真则dp[i] true若i 2且末三个元素构成合法形态全相等或连续递增且dp[i-3]为真则dp[i] true返回dp[n]。多语言实现class Solution: def validPartition(self, nums: List[int]) - bool: dp [False] * (len(nums) 1) dp[0] True for i in range(2, len(nums) 1): if nums[i - 1] nums[i - 2]: dp[i] dp[i] or dp[i - 2] if i 2 and ((nums[i - 1] nums[i - 2] nums[i - 3]) or (nums[i - 3] 1 nums[i - 2] and nums[i - 2] 1 nums[i - 1])): dp[i] dp[i] or dp[i - 3] return dp[len(nums)]public class Solution { public boolean validPartition(int[] nums) { boolean[] dp new boolean[nums.length 1]; dp[0] true; for (int i 2; i nums.length; i) { if (nums[i - 1] nums[i - 2]) { dp[i] dp[i] || dp[i - 2]; } if (i 2 ((nums[i - 1] nums[i - 2] nums[i - 2] nums[i - 3]) || (nums[i - 3] 1 nums[i - 2] nums[i - 2] 1 nums[i - 1]))) { dp[i] dp[i] || dp[i - 3]; } } return dp[nums.length]; } }class Solution { public: bool validPartition(vectorint nums) { vectorbool dp(nums.size() 1, false); dp[0] true; for (int i 2; i nums.size(); i) { if (nums[i - 1] nums[i - 2]) { dp[i] dp[i] || dp[i - 2]; } if (i 2 ((nums[i - 1] nums[i - 2] nums[i - 2] nums[i - 3]) || (nums[i - 3] 1 nums[i - 2] nums[i - 2] 1 nums[i - 1]))) { dp[i] dp[i] || dp[i - 3]; } } return dp[nums.size()]; } };class Solution { /** * param {number[]} nums * return {boolean} */ validPartition(nums) { const dp Array(nums.length 1).fill(false); dp[0] true; for (let i 2; i nums.length; i) { if (nums[i - 1] nums[i - 2]) { dp[i] dp[i] || dp[i - 2]; } if ( i 2 ((nums[i - 1] nums[i - 2] nums[i - 2] nums[i - 3]) || (nums[i - 3] 1 nums[i - 2] nums[i - 2] 1 nums[i - 1])) ) { dp[i] dp[i] || dp[i - 3]; } } return dp[nums.length]; } }public class Solution { public bool ValidPartition(int[] nums) { bool[] dp new bool[nums.Length 1]; dp[0] true; for (int i 2; i nums.Length; i) { if (nums[i - 1] nums[i - 2]) { dp[i] dp[i] || dp[i - 2]; } if (i 2 ((nums[i - 1] nums[i - 2] nums[i - 2] nums[i - 3]) || (nums[i - 3] 1 nums[i - 2] nums[i - 2] 1 nums[i - 1]))) { dp[i] dp[i] || dp[i - 3]; } } return dp[nums.Length]; } }func validPartition(nums []int) bool { dp : make([]bool, len(nums)1) dp[0] true for i : 2; i len(nums); i { if nums[i-1] nums[i-2] { dp[i] dp[i] || dp[i-2] } if i 2 ((nums[i-1] nums[i-2] nums[i-2] nums[i-3]) || (nums[i-3]1 nums[i-2] nums[i-2]1 nums[i-1])) { dp[i] dp[i] || dp[i-3] } } return dp[len(nums)] }class Solution { fun validPartition(nums: IntArray): Boolean { val dp BooleanArray(nums.size 1) dp[0] true for (i in 2..nums.size) { if (nums[i - 1] nums[i - 2]) { dp[i] dp[i] || dp[i - 2] } if (i 2 ((nums[i - 1] nums[i - 2] nums[i - 2] nums[i - 3]) || (nums[i - 3] 1 nums[i - 2] nums[i - 2] 1 nums[i - 1]))) { dp[i] dp[i] || dp[i - 3] } } return dp[nums.size] } }class Solution { func validPartition(_ nums: [Int]) - Bool { var dp Bool dp[0] true for i in 2...nums.count { if nums[i - 1] nums[i - 2] { dp[i] dp[i] || dp[i - 2] } if i 2 ((nums[i - 1] nums[i - 2] nums[i - 2] nums[i - 3]) || (nums[i - 3] 1 nums[i - 2] nums[i - 2] 1 nums[i - 1])) { dp[i] dp[i] || dp[i - 3] } } return dp[nums.count] } }impl Solution { pub fn valid_partition(nums: Veci32) - bool { let n nums.len(); let mut dp vec![false; n 1]; dp[0] true; for i in 2..n { if nums[i - 1] nums[i - 2] { dp[i] dp[i] || dp[i - 2]; } if i 2 ((nums[i - 1] nums[i - 2] nums[i - 2] nums[i - 3]) || (nums[i - 3] 1 nums[i - 2] nums[i - 2] 1 nums[i - 1])) { dp[i] dp[i] || dp[i - 3]; } } dp[n] } }复杂度分析时间复杂度$O(n)$。单次线性扫描空间复杂度$O(n)$。DP 数组长度n1。解法四动态规划空间优化 / Space Optimized直觉Intuition观察自底向上的递推式可以发现计算dp[i]只依赖dp[i-1]、dp[i-2]、dp[i-3]三个前驱状态。既然如此完全没必要保留整个长度为n1的数组只需三个变量滚动即可。原文档给出的实现采用从右向左迭代从倒数第二个索引到 0用三个变量代表位置i、i1、i2的状态每轮迭代后整体移位。仓库中 kotlin/2369-check-if-there-is-a-valid-partition-for-the-array.kt 则提供了另一种等价实现用dp[i % 4]的取模环形数组完成滚动rolling dp O(1) space方向为从左向右同样只保留最近 4 个状态。两种滚动方式思路一致都是只保留必要的历史状态。算法步骤以原文档从右向左版本为例用三个变量表示位置i、i1、i2的 DP 状态初始化数组末尾及超出末尾的位置视为可达true故dp [false, true, true]从倒数第二个索引向0迭代每个位置根据两点计算新状态取2个元素构成合法子数组且后两位状态为真取3个元素构成合法子数组且后三位状态为真迭代结束后移位三个变量返回最终值即整个数组可否被分割。多语言实现class Solution: def validPartition(self, nums: List[int]) - bool: dp [False, True, True] for i in range(len(nums) - 2, -1, -1): dp1 dp[0] if nums[i] nums[i 1] and dp[1]: dp[0] True elif i len(nums) - 2 and dp[2] and ( (nums[i] nums[i 1] nums[i 2]) or (nums[i] 1 nums[i 1] and nums[i 1] nums[i 2] - 1) ): dp[0] True else: dp[0] False dp[2] dp[1] dp[1] dp1 return dp[0]public class Solution { public boolean validPartition(int[] nums) { boolean[] dp new boolean[3]; dp[2] true; dp[1] true; dp[0] false; for (int i nums.length - 2; i 0; i--) { boolean dp1 dp[0]; if (nums[i] nums[i 1] dp[1]) { dp[0] true; } else if (i nums.length - 2 dp[2] ((nums[i] nums[i 1] nums[i] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] nums[i 2] - 1))) { dp[0] true; } else { dp[0] false; } dp[2] dp[1]; dp[1] dp1; } return dp[0]; } }class Solution { public: bool validPartition(vectorint nums) { bool dp[3] {false, true, true}; for (int i nums.size() - 2; i 0; --i) { bool dp1 dp[0]; if (nums[i] nums[i 1] dp[1]) { dp[0] true; } else if (i nums.size() - 2 dp[2] ((nums[i] nums[i 1] nums[i] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] nums[i 2] - 1))) { dp[0] true; } else { dp[0] false; } dp[2] dp[1]; dp[1] dp1; } return dp[0]; } };class Solution { /** * param {number[]} nums * return {boolean} */ validPartition(nums) { let dp [false, true, true]; for (let i nums.length - 2; i 0; i--) { let dp1 dp[0]; if (nums[i] nums[i 1] dp[1]) { dp[0] true; } else if ( i nums.length - 2 dp[2] ((nums[i] nums[i 1] nums[i] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] nums[i 2] - 1)) ) { dp[0] true; } else { dp[0] false; } dp[2] dp[1]; dp[1] dp1; } return dp[0]; } }public class Solution { public bool ValidPartition(int[] nums) { bool[] dp new bool[] { false, true, true }; for (int i nums.Length - 2; i 0; i--) { bool dp1 dp[0]; if (nums[i] nums[i 1] dp[1]) { dp[0] true; } else if (i nums.Length - 2 dp[2] ((nums[i] nums[i 1] nums[i] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] nums[i 2] - 1))) { dp[0] true; } else { dp[0] false; } dp[2] dp[1]; dp[1] dp1; } return dp[0]; } }func validPartition(nums []int) bool { dp : []bool{false, true, true} for i : len(nums) - 2; i 0; i-- { dp1 : dp[0] if nums[i] nums[i1] dp[1] { dp[0] true } else if i len(nums)-2 dp[2] ((nums[i] nums[i1] nums[i] nums[i2]) || (nums[i]1 nums[i1] nums[i1] nums[i2]-1)) { dp[0] true } else { dp[0] false } dp[2] dp[1] dp[1] dp1 } return dp[0] }class Solution { fun validPartition(nums: IntArray): Boolean { val dp booleanArrayOf(false, true, true) for (i in nums.size - 2 downTo 0) { val dp1 dp[0] if (nums[i] nums[i 1] dp[1]) { dp[0] true } else if (i nums.size - 2 dp[2] ((nums[i] nums[i 1] nums[i] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] nums[i 2] - 1))) { dp[0] true } else { dp[0] false } dp[2] dp[1] dp[1] dp1 } return dp[0] } }class Solution { func validPartition(_ nums: [Int]) - Bool { var dp [false, true, true] for i in stride(from: nums.count - 2, through: 0, by: -1) { let dp1 dp[0] if nums[i] nums[i 1] dp[1] { dp[0] true } else if i nums.count - 2 dp[2] ((nums[i] nums[i 1] nums[i] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] nums[i 2] - 1)) { dp[0] true } else { dp[0] false } dp[2] dp[1] dp[1] dp1 } return dp[0] } }impl Solution { pub fn valid_partition(nums: Veci32) - bool { let n nums.len(); let mut dp [false, true, true]; for i in (0..(n as i32 - 2)).rev() { let i i as usize; let dp1 dp[0]; if nums[i] nums[i 1] dp[1] { dp[0] true; } else if i n - 2 dp[2] ((nums[i] nums[i 1] nums[i] nums[i 2]) || (nums[i] 1 nums[i 1] nums[i 1] nums[i 2] - 1)) { dp[0] true; } else { dp[0] false; } dp[2] dp[1]; dp[1] dp1; } dp[0] } }复杂度分析时间复杂度$O(n)$空间复杂度$O(1)$ 额外空间仅常数个状态变量。常见陷阱Common Pitfalls原文档在末尾专门总结了三个高频易错点这里结合递推公式逐一展开陷阱一混淆连续递增与相等的方向三元素子数组允许三元素全相等或三元素连续递增两种情况但二者不可混用。典型错误是写成nums[i] nums[i1] 1这实际在检查递减序列方向恰好反了。# 错误写法nums[i] nums[i1] 1检查的是递减序列 # 正确写法 nums[i] 1 nums[i 1] and nums[i 1] 1 nums[i 2]陷阱二遗漏 2 元素与 3 元素的任一种选择每个位置必须同时考虑取 2 个元素相等和取 3 个元素合法形态两条路。如果只检查一种选择或错误地使用else if把两条互不排斥的路径变成互斥就可能漏掉正确的分割路径——因为取 2 合法不代表取 3 不合法反之亦然。# 必须用 OR 逻辑同时尝试两种选择 res dfs(i 2) if valid_pair else False res res or dfs(i 3) if valid_triple else res陷阱三自底向上 DP 的索引偏移Off-by-One在自底向上版本中dp[i]表示前i个元素即下标0..i-1能否被分割。因此检查末段元素合法性时必须使用nums[i-1]、nums[i-2]、nums[i-3]0 起始下标而不是nums[i]——后者要么越界要么指向了错误的元素。这一点与递归/自顶向下版本中下标即当前位置的语义截然不同是最容易出错的细节。仓库源码印证与延伸阅读本仓库围绕该题提供了完整的文章与实现可直接对照学习解法文章articles/check-if-there-is-a-valid-partition-for-the-array.md本文的原始依据包含四种解法的九种语言完整实现Kotlin 实现kotlin/2369-check-if-there-is-a-valid-partition-for-the-array.kt同一文件内给出了三种变体rolling dp O(1) space采用dp[i % 4]取模环形滚动从左向右迭代第 1-19 行dp O(n) space标准的自底向上填表第 21-35 行recursion带记忆化的递归用IntArray三态缓存-1未计算、0不可行、1可行替代布尔表第 37-59 行。对比可以发现原文档的空间优化版从右向左滚动三个变量而仓库 Kotlin 实现用取模数组从左向右滚动两者殊途同归。理解同一 DP 语义可以有不同的滚动方向与存储技巧有助于你在面试中灵活应对追问。总结Check if There is a Valid Partition For The Array是一道经典的可行性判定型动态规划题四层递进非常清晰解法递推方向时间复杂度空间复杂度适用场景递归从头向后自顶向下无缓存$O(2^n)$$O(n)$理解问题结构DPTop-Down从头向后 记忆化$O(n)$$O(n)$思路最直观的优化版DPBottom-Up从前缀向后缀填表$O(n)$$O(n)$面试常规写法DP空间优化从尾向头滚动三变量$O(n)$$O(1)$追求极致空间掌握了每一步只能取 2 或 3的状态转移骨架以及自底向上版本中dp[i]与数组下标的偏移关系这类能否分割成若干固定长度合法块的问题如区间 DP、字符串分割等变体都可以举一反三、快速迁移。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考