一、动态规划算法的思想与核心概念框架
1. 动态规划的基本思想
动态规划(Dynamic Programming, DP)是一种通过将复杂问题分解为重叠子问题,并利用子问题的解来高效解决原问题的方法。其核心思想是避免重复计算,通过存储中间结果(即 “记忆化”)来优化递归过程,本质上是空间换时间的策略。
与分治法的区别在于:动态规划允许子问题重叠,而分治法要求子问题独立;动态规划通常自底向上求解,而分治法常采用自顶向下递归。
2.核心概念框架
动态规划的核心概念可拆解为以下要素:
- 问题特性
- 最优子结构:问题的最优解包含子问题的最优解(如斐波那契数列中 f (n) 的最优解依赖 f (n-1) 和 f (n-2))
- 重叠子问题:子问题会被重复计算多次(如计算 f (5) 时需要重复计算 f (3))
- 状态定义
- 用dp[i]表示与问题规模i相关的状态,是动态规划的核心建模步骤
- 状态需具备无后效性:当前状态只与之前的状态有关,与后续状态无关
- 状态转移方程
- 描述状态之间的递推关系,是动态规划的数学表达
- 例如:斐波那契数列的转移方程为dp[i] = dp[i-1] + dp[i-2]
- 初始条件
- 定义最小规模子问题的解(如斐波那契数列中dp[0]=0, dp[1]=1)
- 结果提取
- 根据问题要求,从状态数组中获取最终解(可能是dp[n]或数组中的最大值等)
3. 状态转移方程设计方法与技巧
- 设计步骤
- 分析问题结构:确定是否具有最优子结构和重叠子问题
- 定义状态:明确dp[i]表示的含义(关键在于 “i” 的语义)
- 推导转移关系:从子问题解构建当前问题解
- 设定初始条件:处理边界情况
- 确定计算顺序:自底向上填充状态数组
- 核心技巧
- 一维状态转移
- 适用于子问题仅依赖前 1 或前 k 个状态的场景
- 技巧:用滚动数组优化空间(如斐波那契数列只需保存前两个值)
- 二维状态转移
- 适用于双维度约束问题(如背包问题的 “重量” 和 “价值”)
- 技巧:注意遍历顺序(按行或按列),避免状态覆盖
- 区间 DP
- 状态定义为dp[i][j]表示区间 [i,j] 的最优解
- 转移方程:dp[i][j] = max(dp[i][k] + dp[k+1][j] + …),其中 k 为区间分割点
- 状态压缩
- 当状态只与前几行 / 列相关时,用一维数组替代二维数组
- 例如:完全背包问题中用 “倒序遍历” 实现空间优化
- 记忆化搜索(自顶向下)
- 用递归 + 缓存实现动态规划,适合子问题调用顺序不明确的场景
- LeetCode 中可用@lru_cache装饰器快速实现
- 一维状态转移
二、股票问题的动态规划解法框架
股票买卖问题是动态规划的经典应用场景,通过调整交易次数限制、冷冻期、手续费等条件,可以衍生出多种变体。下面给出股票问题的通用解法框架,并针对不同变体详细分析状态转移方程和代码实现。
2.1 通用解法框架
状态定义:
dp[i][k][0]:第 i 天结束,最多完成 k 笔交易,当前不持有股票的最大利润
dp[i][k][1]:第 i 天结束,最多完成 k 笔交易,当前持有股票的最大利润
通用转移方程:
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) # 不操作 or 卖出
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) # 不操作 or 买入(消耗一笔交易)
初始条件:
dp[0][k][0] = 0 # 第0天不持有,利润为0,所有k
dp[0][k][1] = -prices[0] # 第0天持有,说明买入了,利润为负
dp[i][0][0] = 0 # k=0表示不能交易,利润为0
dp[i][0][1] = -∞ # 不可能持有股票(无法交易),买入算一次交易
最终结果:
dp[n-1][K][0],其中 n 为天数,K 为最大交易次数上限
2.2 具体变体及实现
1. 买卖股票的最佳时机(LeetCode 121,最多 1 次交易)
状态转移方程:
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], -prices[i]) # k=0时利润为0,故简化为-prices[i]
空间优化后的代码
def maxProfit(prices):n = len(prices)if n == 0:return 0dp_i_0 = 0dp_i_1 = float('-inf')for i in range(n):dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])dp_i_1 = max(dp_i_1, -prices[i])return dp_i_0
其实本题还可以从贪心算法理解,dp_i_1记录当前最小股票价格,即最大的max(do_i_1, -prices[i]),然后没过一天记录如果卖掉的最大收益,即max(dp_i_0, dp_i_1 + prices[i])。
2. 买卖股票的最佳时机 II(LeetCode 122,不限交易次数)
状态转移方程:
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
# 由于k不限制,可以省略k维度,简化为:
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
空间优化后的代码
def maxProfit(prices):n = len(prices)if n == 0:return 0dp_i_0 = 0dp_i_1 = float('-inf')for i in range(n):temp = dp_i_0dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])dp_i_1 = max(dp_i_1, temp - prices[i])return dp_i_0
3. 买卖股票的最佳时机 III(LeetCode 123,最多 2 次交易)
其实限制次数的股票问题类似于背包问题,要考虑两种约束。具体背包问题下面介绍。
状态转移方程:
dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])
dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], -prices[i]) # 初始买入时k=0,利润为0
空间优化后的代码
def maxProfit(prices):n = len(prices)if n == 0:return 0# 初始化四个状态dp_i10 = 0 # 第一次卖出dp_i11 = float('-inf') # 第一次买入dp_i20 = 0 # 第二次卖出dp_i21 = float('-inf') # 第二次买入for i in range(n):dp_i20 = max(dp_i20, dp_i21 + prices[i])dp_i21 = max(dp_i21, dp_i10 - prices[i])dp_i10 = max(dp_i10, dp_i11 + prices[i])dp_i11 = max(dp_i11, -prices[i])return dp_i20
4. 买卖股票的最佳时机 IV(LeetCode 188,最多 k 次交易)
状态转移方程:
与通用框架一致,但需处理 k 过大导致内存溢出的问题(当 k >= n/2 时,等价于不限次数交易)
代码实现
def maxProfit(k, prices):n = len(prices)if n == 0 or k == 0:return 0# 当k >= n/2时,等价于不限次数交易,用贪心算法if k >= n // 2:profit = 0for i in range(1, n):if prices[i] > prices[i-1]:profit += prices[i] - prices[i-1]return profit# 否则使用动态规划dp = [[[0] * 2 for _ in range(k+1)] for __ in range(n)]for i in range(n):for j in range(1, k+1):if i == 0:dp[0][j][0] = 0dp[0][j][1] = -prices[0]continuedp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])return dp[n-1][k][0]
5. 最佳买卖股票时机含冷冻期(LeetCode 309,不限次数但卖出后需冷冻 1 天)
状态定义扩展:
- dp[i][0]:第 i 天结束不持有且不在冷冻期的最大利润
- dp[i][1]:第 i 天结束持有股票的最大利润
- dp[i][2]:第 i 天结束不持有且在冷冻期的最大利润
状态转移方程:
dp[i][0] = max(dp[i-1][0], dp[i-1][2]) # 前一天不持有(无论是否冷冻)
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) # 前一天持有 或 前一天不冷冻今天买入
dp[i][2] = dp[i-1][1] + prices[i] # 前一天持有今天卖出,进入冷冻期
空间优化后的代码
def maxProfit(prices):n = len(prices)if n == 0:return 0dp_i_0 = 0 # 不持有且不在冷冻期dp_i_1 = float('-inf') # 持有dp_i_2 = 0 # 不持有且在冷冻期for i in range(n):temp = dp_i_0dp_i_0 = max(dp_i_0, dp_i_2)dp_i_1 = max(dp_i_1, temp - prices[i])dp_i_2 = dp_i_1 + prices[i]return max(dp_i_0, dp_i_2)
6. 买卖股票的最佳时机含手续费(LeetCode 714,不限次数但每次交易有手续费)
状态转移方程:
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee) # 卖出时扣除手续费
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
空间优化后的代码
def maxProfit(prices, fee):n = len(prices)if n == 0:return 0dp_i_0 = 0dp_i_1 = float('-inf')for i in range(n):temp = dp_i_0dp_i_0 = max(dp_i_0, dp_i_1 + prices[i] - fee)dp_i_1 = max(dp_i_1, temp - prices[i])return dp_i_0
三、总结与扩展技巧
状态设计技巧:
当问题引入新限制(如冷冻期、手续费)时,可扩展状态维度或新增状态变量
对于交易次数 k,若 k 较大(k >= n/2),可转化为不限次数问题以优化空间
空间优化策略:
当状态转移仅依赖前一天的状态时,可用常数级变量替代二维数组
对于多状态问题(如含冷冻期),维护多个变量记录不同状态
初始化注意事项:
持有股票状态初始化为负无穷,表示初始不可能持有股票
交易次数为 0 时,利润必须为 0,持有状态为负无穷
掌握这些模式后,遇到新的股票问题变体时,只需调整状态定义和转移方程即可快速解决。
三、背包问题详解:从基础到进阶
背包问题是动态规划中的经典问题类型,其核心是在资源有限的情况下最大化收益。下面将从最基础的 0-1 背包问题开始,逐步引入变种和优化方法。
3.1 0-1 背包问题(基础模型)
问题描述:
给定一组物品,每个物品有重量w[i]和价值v[i],以及一个容量为C的背包。要求选择若干物品放入背包,使得总重量不超过容量C,且总价值最大。每个物品只能选择一次(0-1 选择)。
状态定义:
dp[i][j]表示前i个物品放入容量为j的背包中能获得的最大价值。准确地来说应该是考虑前i个物品(前i个物品可供选择的情况下),即并非前i个物品都要放入背包。
状态转移方程:
dp[i][j] = max(dp[i-1][j], # 不选第i个物品dp[i-1][j-w[i]] + v[i] # 选第i个物品(前提是j >= w[i]))
初始条件:
- dp[0][j] = 0:没有物品时,价值为 0
- dp[i][0] = 0:背包容量为 0 时,价值为 0
代码实现:
def knapsack_01(weights, values, C):n = len(weights)dp = [[0] * (C + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, C + 1):if j < weights[i-1]:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])return dp[n][C]
复杂度分析:
- 时间复杂度:O (nC)
- 空间复杂度:O (nC)
3.2 空间优化:滚动数组
观察状态转移方程,发现dp[i][j]只依赖于dp[i-1][j]和dp[i-1][j-w[i]],即只与上一行有关。因此可以用一维数组优化空间:
优化后状态转移方程:
dp[j] = max(dp[j], dp[j-w[i]] + v[i]) # 逆序更新j
代码实现
def knapsack_01_optimized(weights, values, C):n = len(weights)dp = [0] * (C + 1)for i in range(n):for j in range(C, weights[i] - 1, -1): # 逆序遍历,避免重复选择同一物品dp[j] = max(dp[j], dp[j - weights[i]] + values[i])return dp[C]
复杂度分析:
- 时间复杂度:O (nC)
- 空间复杂度:O ©
3.3 完全背包问题
问题描述:
与 0-1 背包的区别在于,每种物品可以无限次选取。
状态转移方程:
dp[i][j] = max(dp[i-1][j], # 不选第i个物品dp[i][j-w[i]] + v[i] # 选第i个物品(可重复选,因此是dp[i]而非dp[i-1]))
一维数组优化
dp[j] = max(dp[j], dp[j-w[i]] + v[i]) # 正序更新j
代码实现
def knapsack_complete(weights, values, C):n = len(weights)dp = [0] * (C + 1)for i in range(n):for j in range(weights[i], C + 1): # 正序遍历,允许重复选择同一物品dp[j] = max(dp[j], dp[j - weights[i]] + values[i])return dp[C]
3.4 多重背包问题
问题描述:
每种物品有有限的数量count[i],可以选择 0 到count[i]次。
朴素解法:
将每种物品拆分成count[i]个独立物品,转化为 0-1 背包问题。
二进制优化:
将每种物品拆分成若干组,每组代表一个二进制数,从而将时间复杂度从 O(nC∑count[i])O (nC\sum count [i])O(nC∑count[i]) 优化到 O(nC∑log(count[i]))O (nC\sum \log (count [i]))O(nC∑log(count[i]))。
代码实现
def knapsack_multi(weights, values, counts, C):n = len(weights)dp = [0] * (C + 1)for i in range(n):weight, value, count = weights[i], values[i], counts[i]# 二进制拆分k = 1while k <= count:# 0-1背包处理拆分后的物品for j in range(C, k * weight - 1, -1):dp[j] = max(dp[j], dp[j - k * weight] + k * value)count -= kk *= 2# 处理剩余物品if count > 0:for j in range(C, count * weight - 1, -1):dp[j] = max(dp[j], dp[j - count * weight] + count * value)return dp[C]
3.5 二维费用背包问题
问题描述:
选择物品除了重量限制外,还有第二个维度的费用限制(如体积)。
状态定义:
dp[i][j][k]表示前i个物品,在重量不超过j且体积不超过k的情况下的最大价值。
状态转移方程:
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-w[i]][k-v[i]] + value[i] # 前提是j >= w[i]且k >= v[i])
一维数组优化
for i in range(n):for j in range(C, w[i]-1, -1): # 重量维度逆序for k in range(D, v[i]-1, -1): # 体积维度逆序dp[j][k] = max(dp[j][k], dp[j-w[i]][k-v[i]] + value[i])
3.6 分组背包问题
问题描述:
物品被分成若干组,每组内的物品互斥,最多只能选一个。
状态转移方程:
dp[k][j] = max(dp[k-1][j], max(dp[k-1][j-w[i]] + v[i] for i in group[k]))
代码实现
def knapsack_group(groups, weights, values, C):n = len(groups) # 组数dp = [0] * (C + 1)for k in range(n):for j in range(C, -1, -1): # 逆序遍历容量for i in groups[k]: # 遍历组内物品if j >= weights[i]:dp[j] = max(dp[j], dp[j - weights[i]] + values[i])return dp[C]
3.7 背包问题变种总结
问题类型 | 核心区别 | 状态转移关键 |
---|---|---|
0-1 背包 | 每个物品选 0 或 1 次 | 逆序遍历容量 |
完全背包 | 每个物品可重复选 | 正序遍历容量 |
多重背包 | 每个物品有数量限制 | 二进制拆分后转为 0-1 背包 |
二维费用背包 | 增加第二个费用维度 | 增加一维状态 |
分组背包 | 物品分组,每组最多选一个 | 组间顺序遍历,组内逆序遍历容量 |
3.8 解题步骤建议
明确问题类型:判断是 0-1 背包、完全背包还是其他变种。
定义状态:通常dp[i][j]表示前i个物品在容量j下的最优解。
推导转移方程:根据物品选取规则确定状态转移方式。
处理边界条件:初始化dp[0][j]和dp[i][0]。
优化空间:若状态转移仅依赖上一行,考虑用一维数组优化。
3.9 LeetCode 相关题目
- Leetcode 416. 分割等和子集(0-1 背包)
目标:判断能否将数组分割成两个子集,使得它们的和相等。
提示:转化为背包问题,容量为总和的一半。 - Leetcode 322. 零钱兑换(完全背包)
目标:用最少的硬币凑成目标金额。
提示:状态定义为dp[i]表示凑成金额i所需的最少硬币数。 - Leetcode 474. 一和零(二维费用背包)
目标:用最多的m个 0 和n个 1 组成最多的字符串。
提示:每个字符串的 0 和 1 数量作为两个费用维度。 - Leetcode 1155. 掷骰子的 N 种方法(分组背包)
目标:计算掷d个骰子,每个骰子有f个面,得到目标和的方法数。
提示:每个骰子作为一组,组内选择一个面。
通过掌握背包问题的基本模型和优化方法,可以解决许多资源分配类的动态规划问题。关键在于准确识别问题类型,并灵活调整状态定义和转移方程。
四、其他动态规划问题
4.1 编辑距离问题(LeetCode 72)
问题描述
给定两个单词 word1 和 word2 ,计算出将 word1 转换成 word2 所使用的最少操作数 。可以进行的操作有插入一个字符、删除一个字符、替换一个字符。
状态定义
设 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。
状态转移方程
- 当 i = 0 时,dp[0][j] = j,表示将空字符串转换为 word2 的前 j 个字符,需要插入 j 个字符。
- 当 j = 0 时,dp[i][0] = i,表示将 word1 的前 i 个字符转换为空字符串,需要删除 i 个字符。
- 当 word1[i - 1] == word2[j - 1] 时,dp[i][j] = dp[i - 1][j - 1],此时不需要进行额外操作。
- 当 word1[i - 1] != word2[j - 1] 时,dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1) ,分别对应替换、删除、插入操作。
代码实现
def minDistance(word1, word2):m, n = len(word1), len(word2)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(m + 1):dp[i][0] = ifor j in range(n + 1):dp[0][j] = jfor i in range(1, m + 1):for j in range(1, n + 1):if word1[i - 1] == word2[j - 1]:dp[i][j] = dp[i - 1][j - 1]else:dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1return dp[m][n]
4.2 最长公共子序列问题(LeetCode 1143)
问题描述
给定两个字符串 text1 和 text2 ,返回这两个字符串的最长公共子序列的长度。子序列是一个可以由另一个序列删除一些元素(也可以不删除)但不改变剩余元素顺序得到的新序列。
状态定义
设 dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。
状态转移方程
- 当 i = 0 或 j = 0 时,dp[i][j] = 0,因为至少有一个字符串为空,最长公共子序列长度为 0。
- 当 text1[i - 1] == text2[j - 1] 时,dp[i][j] = dp[i - 1][j - 1] + 1 。
- 当 text1[i - 1] != text2[j - 1] 时,dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 。
代码实现
def longestCommonSubsequence(text1, text2):m, n = len(text1), len(text2)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(1, m + 1):for j in range(1, n + 1):if text1[i - 1] == text2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[m][n]
4.3 最大子序和问题(LeetCode 53)
问题描述
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
状态定义
设 dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。
状态转移方程
dp[i] = max(dp[i - 1] + nums[i], nums[i]) ,即要么将当前元素加入到前面的子数组中,要么以当前元素作为新的子数组开始。
代码实现
def maxSubArray(nums):n = len(nums)dp = [0] * ndp[0] = nums[0]result = dp[0]for i in range(1, n):dp[i] = max(dp[i - 1] + nums[i], nums[i])result = max(result, dp[i])return result
其实本题从动态规划的角度来看只依赖dp[i-1],即上一个状态,也可以从贪心算法角度理解。每一步计算当前累积和,如果当前累积和小于0,不如直接从当前位置开始再次累积。并在每步存储当前计算得到的最大子序和。
4.4 最长上升子序列(LIS)问题
问题描述
给定一个无序的整数数组,找到其中最长上升子序列的长度。子序列是一个可以由另一个序列删除一些元素(也可以不删除)但不改变剩余元素顺序得到的新序列。
状态定义
设 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。
状态转移方程
- 初始化:dp[i] = 1 ,因为每个元素自身都可以构成一个长度为 1 的上升子序列。
- 对于 i > 0 ,遍历 0 到 i - 1 的元素,如果 nums[j] < nums[i] ,则 dp[i] = max(dp[i], dp[j] + 1) ,表示如果能找到前面比当前元素小的元素,就可以将当前元素接到其对应的最长上升子序列后面,更新当前位置的最长上升子序列长度。
- 当前状态依赖前面所有状态,可以想象,在状态转移图中任何一个状态可以转到之后的状态(对比马尔可夫性质,当前状态只依赖前一个状态)。
代码实现
def lengthOfLIS(nums):n = len(nums)dp = [1] * nfor i in range(n):for j in range(i):if nums[j] < nums[i]:dp[i] = max(dp[i], dp[j] + 1)return max(dp) if dp else 0
4.5 硬币找零 - 最少硬币数(另一种视角)
问题描述
给定不同面额的硬币数组 coins 和一个总金额 amount ,计算凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
状态定义
设 dp[i] 表示凑成金额 i 所需的最少硬币个数。
状态转移方程
- 初始化:dp[0] = 0 ,表示凑成金额 0 需要 0 个硬币;对于其他金额 i ,初始化为一个较大的值(如 amount + 1 ),方便后续取最小值比较。
- 对于每个金额 i ,遍历所有硬币面额 coin ,如果 i >= coin ,则 dp[i] = min(dp[i], dp[i - coin] + 1) ,表示在能使用该硬币的情况下,取使用该硬币和不使用该硬币时的较小硬币数。
代码实现
def coinChange(coins, amount):dp = [amount + 1] * (amount + 1)dp[0] = 0for i in range(1, amount + 1):for coin in coins:if i >= coin:dp[i] = min(dp[i], dp[i - coin] + 1)return dp[amount] if dp[amount] != amount + 1 else -1
类似完全背包问题,不同的是背包问题容量限制是不超过即可,本题硬币找零需要恰好满足。
4.6 分割等和之集
问题描述
给定一个只包含正整数的非空数组 nums 。判断能否将这个数组分割成两个子集,使得两个子集的元素和相等。
解题思路
这道题可以转化为 0 - 1 背包问题。
- 目标转换:要使数组能分割成两个元素和相等的子集,那么数组所有元素的和 sum(nums) 必须是偶数(因为两个子集和相等,总和必然能被 2 整除),然后问题就变为能否从数组中选取一些元素,使得它们的和等于 sum(nums) / 2 。
- 类比背包:可以把 sum(nums) / 2 看作背包的容量,数组中的每个元素 nums[i] 看作物品的重量,同时也是物品的价值(因为选取了这个元素,就得到了它对应的价值,且重量就是它本身的值 ),判断是否能装满背包(即是否能找到元素和等于 sum(nums) / 2 的子集 )。
状态定义
- 设 dp[i][j] 表示从数组的前 i 个元素中选取一些元素,能否使它们的和等于 j 。如果能,dp[i][j] 为 True ,否则为 False 。
状态转移方程
- 不选第 i 个元素:如果前 i - 1 个元素已经能组成和为 j ,那么不选第 i 个元素也能满足,即 dp[i][j] = dp[i - 1][j] 。
- 选第 i 个元素:前提是 j >= nums[i - 1] (因为数组下标从 0 开始,这里 nums[i - 1] 表示第 i 个元素 ),此时如果前 i - 1 个元素能组成和为 j - nums[i - 1] ,那么选上第 i 个元素就能组成和为 j ,即 dp[i][j] = dp[i - 1][j - nums[i - 1]] 。
- 综合起来,状态转移方程为:
- 当 j < nums[i - 1] 时,dp[i][j] = dp[i - 1][j];
- 当 j >= nums[i - 1] 时,dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]] 。
初始条件
- dp[0][0] = True ,表示没有元素时,和为 0 是可以实现的。
对于 j > 0 ,dp[0][j] = False ,因为没有元素时,无法组成大于 0 的和。
代码实现
def canPartition(nums):total = sum(nums)if total % 2 != 0:return Falsetarget = total // 2dp = [False] * (target + 1)dp[0] = Truefor num in nums:for j in range(target, num - 1, -1):dp[j] = dp[j] or dp[j - num]return dp[target]