1. 动态规划基础概念解析动态规划(Dynamic Programming)是一种解决复杂问题的算法思想它通过将原问题分解为相对简单的子问题来求解。这种方法特别适用于具有重叠子问题和最优子结构性质的问题。动态规划的核心思想可以概括为三个关键步骤定义状态明确问题的子问题是什么并用状态表示状态转移方程确定状态之间的关系边界条件确定最小子问题的解1.1 动态规划的基本特征动态规划问题通常具备以下两个重要特征最优子结构一个问题的最优解包含其子问题的最优解重叠子问题在递归求解过程中相同的子问题会被多次计算以经典的斐波那契数列为例计算fib(5)需要计算fib(4)和fib(3)而计算fib(4)又需要计算fib(3)和fib(2)这里fib(3)就被重复计算了。1.2 动态规划的两种实现方式动态规划通常有两种实现方式自顶向下的备忘录法记忆化搜索自底向上的迭代法记忆化搜索保留了递归的直观性同时通过存储已计算结果避免重复计算。而迭代法则通常具有更好的空间效率往往能进一步优化空间复杂度。2. 动态规划入门例题详解2.1 爬楼梯问题问题描述假设你正在爬楼梯每次可以爬1或2个台阶。问爬到第n阶有多少种不同的方法。状态定义设dp[i]表示爬到第i阶的方法数状态转移方程 dp[i] dp[i-1] dp[i-2]边界条件 dp[0] 1 dp[1] 1代码实现def climbStairs(n): if n 1: return 1 dp [0] * (n 1) dp[0], dp[1] 1, 1 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]空间优化由于当前状态只依赖前两个状态可将空间复杂度优化到O(1)def climbStairs(n): if n 1: return 1 a, b 1, 1 for _ in range(2, n 1): a, b b, a b return b2.2 最大子数组和问题问题描述给定一个整数数组nums找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。状态定义dp[i]表示以nums[i]结尾的最大子数组和状态转移方程 dp[i] max(nums[i], dp[i-1] nums[i])边界条件 dp[0] nums[0]代码实现def maxSubArray(nums): n len(nums) dp [0] * n dp[0] nums[0] max_sum dp[0] for i in range(1, n): dp[i] max(nums[i], dp[i-1] nums[i]) max_sum max(max_sum, dp[i]) return max_sum空间优化def maxSubArray(nums): max_sum current_sum nums[0] for num in nums[1:]: current_sum max(num, current_sum num) max_sum max(max_sum, current_sum) return max_sum3. 01背包问题解析3.1 问题描述给定n件物品和一个容量为W的背包。第i件物品的重量为w[i]价值为v[i]。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量且总价值最大。3.2 动态规划解法状态定义dp[i][j]表示前i件物品放入容量为j的背包可以获得的最大价值状态转移方程 dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) (j w[i])边界条件 dp[0][j] 0 (0 j W) dp[i][0] 0 (0 i n)代码实现def knapsack(W, w, v): n len(w) dp [[0] * (W 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, W 1): if j w[i-1]: dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i-1]] v[i-1]) else: dp[i][j] dp[i-1][j] return dp[n][W]3.3 空间优化观察状态转移方程可以发现dp[i][j]只依赖于dp[i-1][...]因此可以优化为一维数组def knapsack(W, w, v): n len(w) dp [0] * (W 1) for i in range(n): for j in range(W, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[W]注意内层循环必须逆序进行否则会重复计算同一物品多次4. 动态规划解题技巧4.1 识别动态规划问题问题可以分解为若干子问题子问题之间有重叠具有最优子结构性质4.2 解题步骤定义状态明确dp数组的含义确定状态转移方程找出状态之间的关系初始化边界条件确定计算顺序考虑空间优化4.3 常见错误与调试技巧数组越界特别注意边界条件的处理状态转移方程错误通过小规模测试用例验证空间优化时的顺序错误如01背包问题必须逆序更新初始化不当确保所有可能的状态都被正确初始化4.4 经典问题分类线性DP最长递增子序列、最大子数组和等区间DP矩阵链乘法、石子合并等背包问题01背包、完全背包、多重背包等树形DP在树结构上的动态规划状态压缩DP使用位运算表示状态5. 动态规划进阶例题5.1 最长递增子序列(LIS)问题描述给定一个无序的整数数组找到其中最长严格递增子序列的长度。状态定义dp[i]表示以nums[i]结尾的最长递增子序列长度状态转移方程 dp[i] max(dp[j] 1) for all j i and nums[j] nums[i]代码实现def lengthOfLIS(nums): if not nums: return 0 dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)优化解法O(nlogn)的贪心二分查找算法def lengthOfLIS(nums): tails [] for num in nums: left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid if left len(tails): tails.append(num) else: tails[left] num return len(tails)5.2 编辑距离问题描述给定两个单词word1和word2计算将word1转换成word2所使用的最少操作数。操作包括插入、删除、替换字符。状态定义dp[i][j]表示word1前i个字符转换为word2前j个字符的最小操作数状态转移方程 如果word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] 否则: dp[i][j] min( dp[i-1][j] 1, # 删除 dp[i][j-1] 1, # 插入 dp[i-1][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] i for j in range(n 1): dp[0][j] j for 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], dp[i][j-1], dp[i-1][j-1]) 1 return dp[m][n]6. 动态规划常见问题解答6.1 如何判断一个问题是否适合用动态规划解决检查问题是否可以分解为子问题验证是否具有最优子结构性质确认是否存在重叠子问题尝试写出递归关系式6.2 动态规划与分治法的区别是什么分治法将问题分解为互不重叠的子问题而动态规划处理的是有重叠的子问题。动态规划通过记忆化存储避免了重复计算。6.3 如何优化动态规划的空间复杂度观察状态转移方程看当前状态是否只依赖于有限的前驱状态使用滚动数组技术对于多维DP考虑是否可以降低维度6.4 动态规划的时间复杂度如何分析通常时间复杂度 状态数 × 每个状态的转移次数。例如二维DP表大小为n×m每个状态转移需要O(1)时间则总时间复杂度为O(nm)。7. 动态规划实战技巧7.1 状态设计技巧根据问题特点选择合适的状态表示有时需要增加状态维度来满足无后效性对于复杂问题可以先用递归思路再转化为DP7.2 边界条件处理明确最小子问题的解考虑空集、零值等特殊情况初始化时注意数组大小和初始值7.3 调试方法打印DP表观察中间结果使用小规模测试用例验证对比递归解和迭代解的结果7.4 性能优化减少不必要的状态转移利用数学性质简化状态转移方程考虑是否可以贪心或二分查找优化在实际应用中动态规划往往需要结合具体问题特点进行灵活调整。掌握核心思想后通过大量练习可以逐渐培养出解决问题的直觉。
1. 动态规划基础概念解析动态规划(Dynamic Programming)是一种解决复杂问题的算法思想它通过将原问题分解为相对简单的子问题来求解。这种方法特别适用于具有重叠子问题和最优子结构性质的问题。动态规划的核心思想可以概括为三个关键步骤定义状态明确问题的子问题是什么并用状态表示状态转移方程确定状态之间的关系边界条件确定最小子问题的解1.1 动态规划的基本特征动态规划问题通常具备以下两个重要特征最优子结构一个问题的最优解包含其子问题的最优解重叠子问题在递归求解过程中相同的子问题会被多次计算以经典的斐波那契数列为例计算fib(5)需要计算fib(4)和fib(3)而计算fib(4)又需要计算fib(3)和fib(2)这里fib(3)就被重复计算了。1.2 动态规划的两种实现方式动态规划通常有两种实现方式自顶向下的备忘录法记忆化搜索自底向上的迭代法记忆化搜索保留了递归的直观性同时通过存储已计算结果避免重复计算。而迭代法则通常具有更好的空间效率往往能进一步优化空间复杂度。2. 动态规划入门例题详解2.1 爬楼梯问题问题描述假设你正在爬楼梯每次可以爬1或2个台阶。问爬到第n阶有多少种不同的方法。状态定义设dp[i]表示爬到第i阶的方法数状态转移方程 dp[i] dp[i-1] dp[i-2]边界条件 dp[0] 1 dp[1] 1代码实现def climbStairs(n): if n 1: return 1 dp [0] * (n 1) dp[0], dp[1] 1, 1 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]空间优化由于当前状态只依赖前两个状态可将空间复杂度优化到O(1)def climbStairs(n): if n 1: return 1 a, b 1, 1 for _ in range(2, n 1): a, b b, a b return b2.2 最大子数组和问题问题描述给定一个整数数组nums找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。状态定义dp[i]表示以nums[i]结尾的最大子数组和状态转移方程 dp[i] max(nums[i], dp[i-1] nums[i])边界条件 dp[0] nums[0]代码实现def maxSubArray(nums): n len(nums) dp [0] * n dp[0] nums[0] max_sum dp[0] for i in range(1, n): dp[i] max(nums[i], dp[i-1] nums[i]) max_sum max(max_sum, dp[i]) return max_sum空间优化def maxSubArray(nums): max_sum current_sum nums[0] for num in nums[1:]: current_sum max(num, current_sum num) max_sum max(max_sum, current_sum) return max_sum3. 01背包问题解析3.1 问题描述给定n件物品和一个容量为W的背包。第i件物品的重量为w[i]价值为v[i]。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量且总价值最大。3.2 动态规划解法状态定义dp[i][j]表示前i件物品放入容量为j的背包可以获得的最大价值状态转移方程 dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) (j w[i])边界条件 dp[0][j] 0 (0 j W) dp[i][0] 0 (0 i n)代码实现def knapsack(W, w, v): n len(w) dp [[0] * (W 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, W 1): if j w[i-1]: dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i-1]] v[i-1]) else: dp[i][j] dp[i-1][j] return dp[n][W]3.3 空间优化观察状态转移方程可以发现dp[i][j]只依赖于dp[i-1][...]因此可以优化为一维数组def knapsack(W, w, v): n len(w) dp [0] * (W 1) for i in range(n): for j in range(W, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[W]注意内层循环必须逆序进行否则会重复计算同一物品多次4. 动态规划解题技巧4.1 识别动态规划问题问题可以分解为若干子问题子问题之间有重叠具有最优子结构性质4.2 解题步骤定义状态明确dp数组的含义确定状态转移方程找出状态之间的关系初始化边界条件确定计算顺序考虑空间优化4.3 常见错误与调试技巧数组越界特别注意边界条件的处理状态转移方程错误通过小规模测试用例验证空间优化时的顺序错误如01背包问题必须逆序更新初始化不当确保所有可能的状态都被正确初始化4.4 经典问题分类线性DP最长递增子序列、最大子数组和等区间DP矩阵链乘法、石子合并等背包问题01背包、完全背包、多重背包等树形DP在树结构上的动态规划状态压缩DP使用位运算表示状态5. 动态规划进阶例题5.1 最长递增子序列(LIS)问题描述给定一个无序的整数数组找到其中最长严格递增子序列的长度。状态定义dp[i]表示以nums[i]结尾的最长递增子序列长度状态转移方程 dp[i] max(dp[j] 1) for all j i and nums[j] nums[i]代码实现def lengthOfLIS(nums): if not nums: return 0 dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)优化解法O(nlogn)的贪心二分查找算法def lengthOfLIS(nums): tails [] for num in nums: left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid if left len(tails): tails.append(num) else: tails[left] num return len(tails)5.2 编辑距离问题描述给定两个单词word1和word2计算将word1转换成word2所使用的最少操作数。操作包括插入、删除、替换字符。状态定义dp[i][j]表示word1前i个字符转换为word2前j个字符的最小操作数状态转移方程 如果word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] 否则: dp[i][j] min( dp[i-1][j] 1, # 删除 dp[i][j-1] 1, # 插入 dp[i-1][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] i for j in range(n 1): dp[0][j] j for 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], dp[i][j-1], dp[i-1][j-1]) 1 return dp[m][n]6. 动态规划常见问题解答6.1 如何判断一个问题是否适合用动态规划解决检查问题是否可以分解为子问题验证是否具有最优子结构性质确认是否存在重叠子问题尝试写出递归关系式6.2 动态规划与分治法的区别是什么分治法将问题分解为互不重叠的子问题而动态规划处理的是有重叠的子问题。动态规划通过记忆化存储避免了重复计算。6.3 如何优化动态规划的空间复杂度观察状态转移方程看当前状态是否只依赖于有限的前驱状态使用滚动数组技术对于多维DP考虑是否可以降低维度6.4 动态规划的时间复杂度如何分析通常时间复杂度 状态数 × 每个状态的转移次数。例如二维DP表大小为n×m每个状态转移需要O(1)时间则总时间复杂度为O(nm)。7. 动态规划实战技巧7.1 状态设计技巧根据问题特点选择合适的状态表示有时需要增加状态维度来满足无后效性对于复杂问题可以先用递归思路再转化为DP7.2 边界条件处理明确最小子问题的解考虑空集、零值等特殊情况初始化时注意数组大小和初始值7.3 调试方法打印DP表观察中间结果使用小规模测试用例验证对比递归解和迭代解的结果7.4 性能优化减少不必要的状态转移利用数学性质简化状态转移方程考虑是否可以贪心或二分查找优化在实际应用中动态规划往往需要结合具体问题特点进行灵活调整。掌握核心思想后通过大量练习可以逐渐培养出解决问题的直觉。
