目录
目录
前言
动态规划
一、416分割等和子集
1、题目描述
示例
提示
2、简单理解？
3、暴力法
3.1、能不能用图示意？
3.2、初始化条件？
3.3、边界条件？
3.4、代码逻辑？
3.5、之前见过但没注意到的？
3.6、疑惑点/新知识 ？
3.7、python 代码
4、优化法
4.1、能不能用图示意？
4.2、初始化条件？
4.3、边界条件？
4.4、代码逻辑？
4.5、之前见过但没注意到的？
4.6、疑惑点/新知识 ？
4.7、python 代码
前言
碎碎念：不要问，猜到了，不要说。
本系列《绝境求生》记录转码算法筑基过程，以代码随想录为纲学习，leetcode_hot_100练手，在此记录思考过程，方便过后复现。内容比较粗糙仅便于笔者厘清思路，复盘总结。
刷过的还得再刷3遍 不然白干
提示：以下是本篇文章正文内容
动态规划
将复杂的问题拆解成若干个重叠子问题，通过求解子问题的最优解，逐步推导出原问题的解。可以通过 记忆化 处理避免重复计算子问题来提升效率
状态转移方程，说白了就是找规律，高级一点说法 就是给混沌以秩序。 369 12， dp（n） = dp（n - 1） + 3 。
实战：
把原问题转化为dp问题
状态定义
一、416分割等和子集
1、题目描述
给你一个只包含正整数的非空数组
nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。关键规则：
- 每个元素必须恰好属于其中一个子集（不能不选，也不能重复选）；
- 子集不要求连续，只需元素和相等。
示例
- 示例 1：输入
nums = [1,5,11,5]→ 输出True
- 解释：数组和为
1+5+11+5=22，可分割为[1,5,5]（和 11）和[11]（和 11），满足条件。- 示例 2：输入
nums = [1,2,3,5]→ 输出False
- 解释：数组和为
1+2+3+5=11，是奇数，无法分割为两个和相等的子集；即使和为偶数，也需验证是否能凑出目标和。提示
1 <= nums.length <= 2001 <= nums[i] <= 100
2、简单理解？
两个子集的元素和相等，为数组总和的一半
问题转化为target=sum(nums)//2 看能否从nums中选出若干元素使得和为target。
！！每个元素恰好属于其中一个子集，不能不选，也不能重复选
子集不要求连续。
不适合用双指针，因为元素和没有单调的规律
3、暴力法
暴力法一般都会超时，这题暴力法用递归难想的一批是默写出来的，根本想不到
3.1、能不能用图示意？
以 nums = [1,5,11,5]，target=11 为例 枚举选/不选的状态 递归树（dfs(index, remain)：index为当前遍历索引，remain为剩余目标和）： dfs(0,11) → 选1（remain=10）/ 不选1（remain=11） ├─ dfs(1,10) → 选5（remain=5）/ 不选5（remain=10） │ ├─ dfs(2,5) → 选11（remain=-6，无效）/ 不选11（remain=5） │ │ └─ dfs(3,5) → 选5（remain=0，返回True）/ 不选5（remain=5，返回False） │ └─ ...（不选5的分支最终返回False） └─ ...（不选1的分支也能找到True） 最终返回True
3.2、初始化条件？
记忆缓存字典 key=(index, remain)，value=true/false状态
3.3、边界条件？
判断数组和是否为奇数，是返回False
如果某个单一元素直接大于数组和的一半，直接返回False
3.4、代码逻辑？
问题转化为target=sum(nums)//2 看能否从nums中选出若干元素使得和为target
选当前元素，剩余目标-=当前元素，递归下一个
不选，剩余目标和不变，递归下一个
终止条件。当剩余目标和为0。返回true，如果遍历完所有元素没凑出和为0 返回false
3.5、之前见过但没注意到的？
选和不选这两个状态怎么用代码写出来？ 就像打家劫舍一样偷喝不偷
3.6、疑惑点/新知识 ？
递归函数dfs就想到终止条件
3.7、python 代码
from typing import List class Solution: def canPartition(self, nums: List[int]) -> int: total = sum(nums) # 前置判断1：总和为奇数，直接返回False if total % 2 != 0: return False target = total // 2 # 前置判断2：存在元素大于target，直接返回False if max(nums) > target: return False # 记忆化缓存：key=(index, remain)，value=该状态的结果（True/False） memo = {} # 定义递归函数：遍历到index位置，剩余目标和为remain，返回能否凑出 def dfs(index, remain): # 终止条件1：剩余目标和为0，凑出，返回True if remain == 0: return True # 终止条件2：遍历完所有元素 或 剩余目标和<0，未凑出，返回False if index == len(nums) or remain < 0: return False # 查记忆化缓存，已有结果直接返回 if (index, remain) in memo: return memo[(index, remain)] # 递归分支1：选当前元素，剩余目标和减少nums[index] choose = dfs(index + 1, remain - nums[index]) # 递归分支2：不选当前元素，剩余目标和不变 not_choose = dfs(index + 1, remain) # 两种分支有一个为True，当前状态就为True res = choose or not_choose # 存入缓存，供后续复用 memo[(index, remain)] = res return res # 从索引0、剩余目标和target开始递归 return dfs(0, target)4、优化法
4.1、能不能用图示意？
以 nums = [1,5,11,5]，target=11 为例 # 初始化dp数组（长度12，索引0~11） dp = [True, False, False, False, False, False, False, False, False, False, False, False] # 遍历第一个元素num=1： 逆序遍历j=11→1： j=1: dp[1] = dp[1] or dp[1-1] = False or True → True dp变为：[T, T, F, F, F, F, F, F, F, F, F, F] # 遍历第二个元素num=5： 逆序遍历j=11→5： j=5: dp[5] = F or dp[0] → T j=6: dp[6] = F or dp[1] → T dp变为：[T, T, F, F, F, T, T, F, F, F, F, F] # 遍历第三个元素num=11： 逆序遍历j=11→11： j=11: dp[11] = F or dp[0] → T dp变为：[T, T, F, F, F, T, T, F, F, F, F, T]（已找到True，后续可提前终止） # 遍历第四个元素num=5（无需遍历，结果已确定） 最终dp[11] = True
4.2、初始化条件？
dp[0] 。空子集的时候必满足
4.3、边界条件？
奇数情况，还有某个元素已经大于target的情况
4.4、代码逻辑？
dp[j ] j 代表的是nums中的元素，从数组里挑元素，dp[ j ]表示能否凑出 j 的子集
为什么有时候理解不了？ dp数组是从dp[0]推导出来的，先看dp[1],dp[2] ,dp[ 3 ]
j in range(target, num-1,-1) 逆序遍历速度更快,我们的目的是更新dp数组的状态，所以怎么方便推出dp[1]，dp[2] .......且不重复 就可以用逆序。
状态转移
dp[j] = dp[j] or dp[j - num]：dp[j]：不选当前 num，保持原有状态；dp[j - num]：选当前 num，若 j-num 能凑出，则 j 也能凑出。
- 外层循环
for num in nums：遍历每个元素，每个元素只能处理一次（0-1 背包特性）； - 内层循环
range(target, num-1, -1)：- 逆序遍历是关键！正序遍历会导致同一元素被多次选中（比如 num=1，j=1 更新为 True 后，j=2 会用 j=1 的结果，相当于选了两次 1）；
- 遍历下限是
num：j < num 时，j-num 为负（看状态转移方程有dp[j-num]），无意义，无需遍历。
4.5、之前见过但没注意到的？
1、首先要清楚状态定义，即状态方程的索引还有值对应啥不然会乱
2、dp方程，你就想前一个是啥 依赖dp[i-1]还是dp[i-2]，还是都依赖，还是运算法的依赖,然后想初始化
2、把示意图画出来
4.6、疑惑点/新知识 ？
分割等和子集即为0-1背包问题，就是把分割数组转化为凑目标和背包问题，。需要区分0-1背包元素选一次，还有无限背包元素取多次的遍历顺序差异
牢记！！！ 当前状态是基于之前的状态做决策得到的结果
4.7、python 代码
class Solution: def canPartition(self, nums: List[int]) -> bool: total = sum(nums) # 前置判断1：总和为奇数，无法分割 if total % 2 != 0: return False target = total // 2 # 前置判断2：存在元素大于目标和，无法分割 if max(nums) > target: return False # 步骤1：初始化dp数组 # dp[j]表示能否凑出和为j的子集，长度=target+1（索引0~target） # 边界条件：dp[0] = True（和为0的空集存在），其余初始为False dp = [False] * (target + 1) dp[0] = True # 步骤2：遍历每个元素（0-1背包，每个元素只能选一次） for num in nums: # 步骤3：逆序遍历j（从target到num），避免重复选同一元素 # 若正序遍历，会导致同一元素被多次选中（比如num=1，j=1更新后，j=2会复用j=1的结果，相当于选了两次1） for j in range(target, num - 1, -1): # 状态转移：不选num（dp[j]） 或 选num（dp[j-num]） dp[j] = dp[j] or dp[j - num] # 提前终止：若已找到能凑出target的情况，直接返回True if dp[target]: return True # 步骤4：返回最终结果 return dp[target]顶级命格的强大之处在于**“非线性的爆发力”**
