1. 线性动态规划基础概念解析线性动态规划Linear Dynamic Programming是算法设计中最为基础且重要的技术之一。不同于传统递归的暴力解法动态规划通过存储子问题的解来避免重复计算将指数级时间复杂度优化至多项式级别。其核心特征体现在线性结构上——问题的状态转移沿着单一维度进行形成清晰的递推关系链。典型线性DP问题具有三个关键要素状态定义用dp[i]表示第i个阶段的最优解转移方程明确dp[i]与dp[i-1], dp[i-2]等前驱状态的关系边界条件确定初始状态如dp[0]、dp[1]的取值以经典的斐波那契数列为例def fib(n): dp [0] * (n1) dp[0], dp[1] 0, 1 # 边界条件 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] # 转移方程 return dp[n]这个实现将时间复杂度从递归的O(2^n)降为O(n)空间复杂度O(n)。进一步优化可发现当前状态只依赖前两个状态因此可将空间压缩到O(1)def fib(n): a, b 0, 1 for _ in range(n): a, b b, a b return a2. 线性DP的四大经典模型2.1 最大子数组和问题Kadane算法给定整数数组nums求连续子数组的最大和。这是线性DP的经典应用def maxSubArray(nums): dp [0] * len(nums) dp[0] nums[0] for i in range(1, len(nums)): dp[i] max(nums[i], dp[i-1] nums[i]) return max(dp)空间优化版本def maxSubArray(nums): max_sum curr_sum nums[0] for num in nums[1:]: curr_sum max(num, curr_sum num) max_sum max(max_sum, curr_sum) return max_sum2.2 最长递增子序列LIS求序列中最长的严格递增子序列长度。O(n^2)解法def lengthOfLIS(nums): 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)解法利用二分查找维护递增序列。2.3 背包问题系列0-1背包是DP的入门必修课。设dp[i][j]表示前i件物品放入容量j背包的最大价值def knapsack(W, wt, val): n len(wt) dp [[0]*(W1) for _ in range(n1)] for i in range(1, n1): for w in range(1, W1): if wt[i-1] w: dp[i][w] max(val[i-1]dp[i-1][w-wt[i-1]], dp[i-1][w]) else: dp[i][w] dp[i-1][w] return dp[n][W]2.4 路径计数问题网格路径问题展示DP的二维线性扩展。例如m×n网格从左上到右下的唯一路径数def uniquePaths(m, n): dp [[1]*n for _ in range(m)] for i in range(1, m): for j in range(1, n): dp[i][j] dp[i-1][j] dp[i][j-1] return dp[-1][-1]3. 线性DP的优化技巧3.1 滚动数组压缩空间当状态转移只依赖有限前驱状态时可用滚动数组将空间复杂度从O(n)降至O(1)。以斐波那契为例def fib(n): if n 2: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b3.2 状态机模型某些问题需要同时维护多个状态。如股票买卖问题def maxProfit(prices): n len(prices) dp [[0]*2 for _ in range(n1)] dp[0][1] -float(inf) for i in range(1, n1): dp[i][0] max(dp[i-1][0], dp[i-1][1]prices[i-1]) dp[i][1] max(dp[i-1][1], -prices[i-1]) return dp[n][0]3.3 前缀和优化当转移方程包含区间和时可用前缀和优化。如最大子数组和的另一种写法def maxSubArray(nums): min_prefix prefix 0 max_sum -float(inf) for num in nums: prefix num max_sum max(max_sum, prefix - min_prefix) min_prefix min(min_prefix, prefix) return max_sum4. 线性DP的调试与验证4.1 打印DP表可视化DP表格是调试的最佳方式def print_dp_table(dp): for row in dp: print( .join(f{x:3} for x in row)) # 在路径问题中调用 print_dp_table(dp)4.2 边界条件测试特别注意以下边界情况空输入如空数组单元素输入全正/全负数值极值情况如最大规模输入4.3 转移方程验证通过小规模案例手动计算验证nums [-2,1,-3,4,-1,2,1,-5,4] dp值应依次为 [-2,1,-2,4,3,5,6,1,5] 最大值为65. 线性DP的进阶应用5.1 字符串编辑距离def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]5.2 正则表达式匹配def isMatch(s, p): m, n len(s), len(p) dp [[False]*(n1) for _ in range(m1)] dp[0][0] True for j in range(1, n1): if p[j-1] *: dp[0][j] dp[0][j-2] for i in range(1, m1): for j in range(1, n1): if p[j-1] s[i-1] or p[j-1] .: dp[i][j] dp[i-1][j-1] elif p[j-1] *: dp[i][j] dp[i][j-2] if p[j-2] s[i-1] or p[j-2] .: dp[i][j] | dp[i-1][j] return dp[m][n]5.3 乘积最大子数组def maxProduct(nums): res min_val max_val nums[0] for num in nums[1:]: candidates (num, min_val*num, max_val*num) min_val, max_val min(candidates), max(candidates) res max(res, max_val) return res6. 线性DP的常见误区与修正6.1 错误的状态定义典型错误在LIS问题中试图用dp[i]表示以i结尾的子序列数。正确应表示长度。6.2 遗漏边界条件如斐波那契中忘记处理n0的情况或路径问题中未初始化第一行/列。6.3 转移方向错误二维DP中需明确遍历顺序。如# 正确的路径问题遍历 for i in range(1, m): for j in range(1, n): dp[i][j] dp[i-1][j] dp[i][j-1] # 错误的顺序会导致使用未计算的状态 for j in range(1, n): for i in range(1, m): dp[i][j] dp[i-1][j] dp[i][j-1]7. 线性DP的扩展训练建议从经典问题入手斐波那契→爬楼梯→打家劫舍→股票买卖循序渐进增加维度一维→二维→带状态的多维对比记忆化搜索与递推写法尝试空间优化版本参加编程竞赛如LeetCode周赛实战演练推荐训练题库LeetCode动态规划专题按难度排序《算法导论》第15章动态规划《算法竞赛入门经典》第9章动态规划在实际编码中建议先用记忆化搜索递归缓存思考问题再转化为递推形式。例如斐波那契的记忆化版本from functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 2: return n return fib(n-1) fib(n-2)这种写法更直观能帮助理解状态转移关系再优化为迭代版本。
1. 线性动态规划基础概念解析线性动态规划Linear Dynamic Programming是算法设计中最为基础且重要的技术之一。不同于传统递归的暴力解法动态规划通过存储子问题的解来避免重复计算将指数级时间复杂度优化至多项式级别。其核心特征体现在线性结构上——问题的状态转移沿着单一维度进行形成清晰的递推关系链。典型线性DP问题具有三个关键要素状态定义用dp[i]表示第i个阶段的最优解转移方程明确dp[i]与dp[i-1], dp[i-2]等前驱状态的关系边界条件确定初始状态如dp[0]、dp[1]的取值以经典的斐波那契数列为例def fib(n): dp [0] * (n1) dp[0], dp[1] 0, 1 # 边界条件 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] # 转移方程 return dp[n]这个实现将时间复杂度从递归的O(2^n)降为O(n)空间复杂度O(n)。进一步优化可发现当前状态只依赖前两个状态因此可将空间压缩到O(1)def fib(n): a, b 0, 1 for _ in range(n): a, b b, a b return a2. 线性DP的四大经典模型2.1 最大子数组和问题Kadane算法给定整数数组nums求连续子数组的最大和。这是线性DP的经典应用def maxSubArray(nums): dp [0] * len(nums) dp[0] nums[0] for i in range(1, len(nums)): dp[i] max(nums[i], dp[i-1] nums[i]) return max(dp)空间优化版本def maxSubArray(nums): max_sum curr_sum nums[0] for num in nums[1:]: curr_sum max(num, curr_sum num) max_sum max(max_sum, curr_sum) return max_sum2.2 最长递增子序列LIS求序列中最长的严格递增子序列长度。O(n^2)解法def lengthOfLIS(nums): 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)解法利用二分查找维护递增序列。2.3 背包问题系列0-1背包是DP的入门必修课。设dp[i][j]表示前i件物品放入容量j背包的最大价值def knapsack(W, wt, val): n len(wt) dp [[0]*(W1) for _ in range(n1)] for i in range(1, n1): for w in range(1, W1): if wt[i-1] w: dp[i][w] max(val[i-1]dp[i-1][w-wt[i-1]], dp[i-1][w]) else: dp[i][w] dp[i-1][w] return dp[n][W]2.4 路径计数问题网格路径问题展示DP的二维线性扩展。例如m×n网格从左上到右下的唯一路径数def uniquePaths(m, n): dp [[1]*n for _ in range(m)] for i in range(1, m): for j in range(1, n): dp[i][j] dp[i-1][j] dp[i][j-1] return dp[-1][-1]3. 线性DP的优化技巧3.1 滚动数组压缩空间当状态转移只依赖有限前驱状态时可用滚动数组将空间复杂度从O(n)降至O(1)。以斐波那契为例def fib(n): if n 2: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b3.2 状态机模型某些问题需要同时维护多个状态。如股票买卖问题def maxProfit(prices): n len(prices) dp [[0]*2 for _ in range(n1)] dp[0][1] -float(inf) for i in range(1, n1): dp[i][0] max(dp[i-1][0], dp[i-1][1]prices[i-1]) dp[i][1] max(dp[i-1][1], -prices[i-1]) return dp[n][0]3.3 前缀和优化当转移方程包含区间和时可用前缀和优化。如最大子数组和的另一种写法def maxSubArray(nums): min_prefix prefix 0 max_sum -float(inf) for num in nums: prefix num max_sum max(max_sum, prefix - min_prefix) min_prefix min(min_prefix, prefix) return max_sum4. 线性DP的调试与验证4.1 打印DP表可视化DP表格是调试的最佳方式def print_dp_table(dp): for row in dp: print( .join(f{x:3} for x in row)) # 在路径问题中调用 print_dp_table(dp)4.2 边界条件测试特别注意以下边界情况空输入如空数组单元素输入全正/全负数值极值情况如最大规模输入4.3 转移方程验证通过小规模案例手动计算验证nums [-2,1,-3,4,-1,2,1,-5,4] dp值应依次为 [-2,1,-2,4,3,5,6,1,5] 最大值为65. 线性DP的进阶应用5.1 字符串编辑距离def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]5.2 正则表达式匹配def isMatch(s, p): m, n len(s), len(p) dp [[False]*(n1) for _ in range(m1)] dp[0][0] True for j in range(1, n1): if p[j-1] *: dp[0][j] dp[0][j-2] for i in range(1, m1): for j in range(1, n1): if p[j-1] s[i-1] or p[j-1] .: dp[i][j] dp[i-1][j-1] elif p[j-1] *: dp[i][j] dp[i][j-2] if p[j-2] s[i-1] or p[j-2] .: dp[i][j] | dp[i-1][j] return dp[m][n]5.3 乘积最大子数组def maxProduct(nums): res min_val max_val nums[0] for num in nums[1:]: candidates (num, min_val*num, max_val*num) min_val, max_val min(candidates), max(candidates) res max(res, max_val) return res6. 线性DP的常见误区与修正6.1 错误的状态定义典型错误在LIS问题中试图用dp[i]表示以i结尾的子序列数。正确应表示长度。6.2 遗漏边界条件如斐波那契中忘记处理n0的情况或路径问题中未初始化第一行/列。6.3 转移方向错误二维DP中需明确遍历顺序。如# 正确的路径问题遍历 for i in range(1, m): for j in range(1, n): dp[i][j] dp[i-1][j] dp[i][j-1] # 错误的顺序会导致使用未计算的状态 for j in range(1, n): for i in range(1, m): dp[i][j] dp[i-1][j] dp[i][j-1]7. 线性DP的扩展训练建议从经典问题入手斐波那契→爬楼梯→打家劫舍→股票买卖循序渐进增加维度一维→二维→带状态的多维对比记忆化搜索与递推写法尝试空间优化版本参加编程竞赛如LeetCode周赛实战演练推荐训练题库LeetCode动态规划专题按难度排序《算法导论》第15章动态规划《算法竞赛入门经典》第9章动态规划在实际编码中建议先用记忆化搜索递归缓存思考问题再转化为递推形式。例如斐波那契的记忆化版本from functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 2: return n return fib(n-1) fib(n-2)这种写法更直观能帮助理解状态转移关系再优化为迭代版本。
