一、动态规划算法的思想与核心概念框架

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(nCcount[i]) 优化到 O(nC∑log⁡(count[i]))O (nC\sum \log (count [i]))O(nClog(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]

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/bicheng/88272.shtml
繁体地址,请注明出处:http://hk.pswp.cn/bicheng/88272.shtml
英文地址,请注明出处:http://en.pswp.cn/bicheng/88272.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

阿幸课堂随机点名

代码功能 这个是一个HTML网页端&#xff0c;简单来说就是可以双击之后运行进行点名。 当然&#xff0c;不局限于课堂点名 代码功能 Excel 导入增强&#xff1a; 增加了列选择器&#xff0c;可以指定从哪一列读取学生姓名 增加了起始行选择器&#xff0c;可以跳过标题行或其…

LeetCode 560: 和为K的子数组

题目描述给定一个整数数组 nums 和一个整数 k&#xff0c;请统计并返回该数组中和为 k 的连续子数组的个数。示例 1&#xff1a;输入&#xff1a;nums [1,1,1], k 2 输出&#xff1a;2示例 2&#xff1a;输入&#xff1a;nums [1,2,3], k 3 输出&#xff1a;2提示&#xff…

微软官方C++构建工具:历史演变、核心组件与现代实践指南

引言&#xff1a;C构建工具的战略意义 在Windows生态系统中&#xff0c;​​微软C构建工具​​&#xff08;Microsoft C Build Tools&#xff09;构成了数百万开发者和应用程序的技术基石。从早期的MS-DOS命令行工具到如今支持​​跨平台开发​​的现代化工具链&#xff0c;微…

探索Cocos_CoilTheRope:一款创新的游戏引擎扩展项目

探索Cocos_CoilTheRope&#xff1a;一款创新的游戏引擎扩展项目 去发现同类优质开源项目:https://gitcode.com/ 是一个基于Cocos2d-x游戏引擎的扩展库&#xff0c;旨在为开发者提供一种简便的方法来实现绳子缠绕和物理交互效果。该项目由DreamLXW开发并维护&#xff0c;为游戏…

爬虫-正则表达式

在线正则表达式测试OSCHINA.NET在线工具,ostools为开发设计人员提供在线工具&#xff0c;提供jsbin在线 CSS、JS 调试&#xff0c;在线 Java API文档,在线 PHP API文档,在线 Node.js API文档,Less CSS编译器&#xff0c;MarkDown编译器等其他在线工具https://tool.oschina.net/…

【BTC】数据结构

目录 那比特币区块链的组织形式到底是以链表的形式&#xff0c;还是树的形式呢&#xff1f; 区块头和区块体与默克尔树的关系 默克尔证明详解 区块链和链表最大的区别就是区块链用哈希指针代替了普通指针。 链表的指针就是指向一个结构体在内存中的地址&#xff0c;而哈希指…

飞算 JavaAI:让 Java 开发效率飙升的智能助手,日常开发全场景应用指南

飞算 JavaAI&#xff1a;让 Java 开发效率飙升的智能助手 &#xff0c;日常开发全场景应用指南 在 Java 开发的日常工作中&#xff0c;开发者常常面临各类重复性劳动与逻辑复杂度挑战。飞算 JavaAI 作为专注于 Java 领域的智能开发助手&#xff0c;能够覆盖从代码生成到项目维护…

8.2 文档预处理模块(二)

一、从0开始&#xff1a;简易RAG实现 在构建更复杂的 RAG 架构之前&#xff0c;我们先从最基础的版本入手。整个流程可以分为以下几个关键步骤&#xff1a; 1.数据导入&#xff1a;加载并预处理原始文本数据&#xff0c;为后续处理做好准备。 2.文本分块&#xff1a;将长文本…

【系统与工具】Linux——Linux简介、安装、简单使用

计算机概论与Linux简介 计算机概论Linux介绍与版本 Linux的规划与安装 Linux与硬件平台密切相关规划硬件与Linux安装 主机规划与磁盘分区安装CentOS、多重引导 简单使用 帮助手册文本编辑器关机 0. Linux介绍与版本 操作系统&#xff08;Linux&#xff09;&#xff1a;高效…

从视频数据到数字孪生:如何构建虚拟与现实的桥梁?

概述 视频数据与三维场景融合渲染技术通过将动态视频与静态三维模型结合&#xff0c;利用GPU加速、WebGL渲染、数字孪生等技术&#xff0c;实现虚拟与现实的交互式融合。该技术广泛应用于智慧城市、工业监控、虚拟现实、游戏特效等领域&#xff0c;能够提升场景的直观性和用户沉…

【笔记】开源 AI Agent 项目 V1 版本 [新版] 部署 日志

kortix-ai/suna at v1 一、最新版本号 V1 二、部署截图 本地开发环境仍然依赖于 Poetry 环境&#xff1a; &#xff08;Python>3.11,<3.13&#xff09; 创建本地 Poetry 虚拟环境 Python 多版本环境治理理念驱动的系统架构设计&#xff1a;三维治理、四级隔离、五项自…

NumPy-梯度与导数计算详解

NumPy-梯度与导数计算详解一、梯度与导数的基本概念1. 导数的定义2. 梯度的定义二、NumPy中的梯度计算函数&#xff1a;np.gradient()1. 函数语法2. 一维数组的梯度计算3. 多维数组的梯度计算三、基于梯度的导数近似方法1. 前向差分2. 中心差分四、实际应用场景1. 函数优化2. 数…

Redis架构安全

先学习&#xff1a;Redis架构简介-CSDN博客 Redis压测 Redis一般应用于高并发的场景&#xff0c;所以一定要对Redis的性能做压测。 Redis提供了压测脚本redis-benchmark&#xff0c;可以对Redis进行快速的基准测试。 # 20个线程&#xff0c;100W个请求&#xff0c;测试redi…

自动化Trae Apollo参数解释的批量获取

自动化Trae Apollo参数解释的批量获取一、背景介绍二、设计思路三、操作步骤1. 环境准备2. 获取界面坐标3. 定位关键元素4. 执行自动化查询5. 获取结果四、完整代码五、扩展应用一、背景介绍 在自动驾驶开发中&#xff0c;百度Apollo平台提供了大量参数用于调整系统行为。Trae…

数学模型:十大距离

十大距离 文章目录十大距离定义1. 欧氏距离&#xff08;Euclidean Distance&#xff09;2. 曼哈顿距离&#xff08;Manhattan Distance&#xff09;3. 切比雪夫距离&#xff08;Chebyshev Distance&#xff09;4. 闵可夫斯基距离&#xff08;Minkowski Distance&#xff09;5. …

流水线(Jenkins)打包拉取依赖的时候提示无法拉取,需要登录私仓的解决办法

在日常工作中&#xff0c;遇到了Jenkins拉取部门内部组件库失败的情况&#xff0c;原因是组件库后面放到了阿里云私仓&#xff0c;并且是没有公开的&#xff0c;所以就会有如下提示的&#xff0c;一开始我实在.npmrc文件写死阿里云提供的接入token&#xff0c;后面发现可能是因…

操作系统王道考研习题

1.1.4本节习题精选 一、单项选择题 01&#xff0e;操作系统是对(&#xff09;进行管理的软件。 A.软件 B.硬件 C.计算机资源 D.应用程序 01.c 操作系统管理计算机的硬件和软件资源&#xff0c;这些资源统称为计算机资源。注意&#xff0c;操作系统不仅管理处理机、存储器等硬件…

C语言extern的用法(非常详细,通俗易懂)

以往我们都是将所有的代码写到一个源文件里面&#xff0c;对于小程序&#xff0c;代码不过几百行&#xff0c;这或许无可厚非&#xff0c;但当程序膨胀代码到几千行甚至上万行后&#xff0c;就应该考虑将代码分散到多个文件中&#xff0c;否则代码的阅读和维护将成为一件痛苦的…

Git【开源分布式版本控制工具】安装-配置-常用指令-Git远程仓库-IDEA使用Git

参考博客&#xff1a;Git&#xff08;分布式版本控制工具&#xff09;_为什么哔哩哔哩有些视频没有字幕-CSDN博客 Git就是一个类似于百度云盘的仓库&#xff1b;重点是要掌握使用idea操作Git&#xff0c;企业用的最多&#xff0c;一般不会去使用命令 Git通过不断阶段保存文件…

JavaScript数组键值去重方法

使用 filter 和 Map 根据键值去重我来详细解释方法2&#xff0c;这是一种高效且简洁的数组去重方法&#xff0c;特别适合根据对象中的某个键值进行去重操作。完整代码function uniqueByKey(arr, key) {return [...new Map(arr.map(item > [item[key], item])).values()]; }分…