1. 线性动态规划基础概念线性动态规划Linear Dynamic Programming是动态规划问题中最基础且应用最广泛的一类问题。这类问题的特点是状态转移方程沿着线性结构如数组、序列等进行递推每个状态只与前面有限个状态相关。动态规划本质上是一种通过空间换时间的优化技术它将问题分解为相互重叠的子问题通过存储子问题的解来避免重复计算。线性DP作为动态规划的入门类型其状态转移通常呈现明显的线性特征。关键理解线性DP中的线性指的是问题结构的线性特征而非算法的时间复杂度。即使时间复杂度可能是O(n²)或更高只要状态转移沿着单一维度推进仍属于线性DP范畴。2. 线性DP的三大核心要素2.1 状态定义状态定义是DP问题求解的第一步也是最关键的一步。对于线性DP状态通常表示为dp[i]表示考虑前i个元素时的最优解dp[i][j]当需要额外维度时的状态扩展以经典的爬楼梯问题为例状态定义dp[i]表示到达第i阶楼梯的方法数边界条件dp[0] 1, dp[1] 1状态转移dp[i] dp[i-1] dp[i-2]2.2 状态转移方程状态转移方程体现了子问题之间的关系。设计时需要考虑当前状态如何从已知状态转移得到转移的条件和限制多种转移路径中的最优选择例如在最大子数组和问题中# Kadane算法 dp[i] max(nums[i], dp[i-1] nums[i]) max_sum max(dp)2.3 初始化与边界处理边界条件处理不当会导致整个DP求解失败。常见边界情况包括序列起始位置i0或i1特殊输入空序列、单元素序列非法状态的处理3. 经典线性DP问题解析3.1 最长递增子序列(LIS)问题描述给定数组nums找到最长严格递增子序列的长度。解法def lengthOfLIS(nums): dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] nums[j]: dp[i] max(dp[i], dp[j] 1) return max(dp)时间复杂度O(n²) 空间复杂度O(n)优化思路可以结合二分查找将时间复杂度优化到O(nlogn)3.2 最大子数组和问题描述找出数组中连续子数组的最大和。解法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_sum3.3 编辑距离问题描述计算将word1转换成word2所需的最少操作次数插入、删除、替换。解法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]4. 线性DP的优化技巧4.1 空间复杂度优化当状态转移只依赖有限的前几个状态时可以使用滚动数组或变量压缩空间# 斐波那契数列空间优化 def fib(n): if n 2: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b4.2 状态转移优化对于某些问题可以通过数学分析简化状态转移# 买卖股票最佳时机问题 def maxProfit(prices): min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit4.3 单调队列/栈优化当状态转移可以表示为滑动窗口最值时可以使用单调数据结构优化# 滑动窗口最大值问题 from collections import deque def maxSlidingWindow(nums, k): q deque() res [] for i, num in enumerate(nums): while q and nums[q[-1]] num: q.pop() q.append(i) if q[0] i - k: q.popleft() if i k - 1: res.append(nums[q[0]]) return res5. 线性DP的常见错误与调试技巧5.1 初始化错误典型表现数组越界访问边界条件处理不当初始值设置不合理调试方法打印DP表的初始状态验证边界条件的正确性检查数组大小是否合理5.2 状态转移错误典型表现结果比预期偏大或偏小出现不可能的解重复计算或遗漏情况调试方法打印完整的DP表检查转移条件的逻辑完备性验证转移方程的正确性5.3 空间/时间复杂度爆炸典型表现大输入时内存不足运行时间过长解决方案分析状态依赖关系尝试空间优化寻找问题特性尝试数学优化考虑是否可以转换为贪心算法6. 线性DP的解题模板6.1 一维DP模板def linear_dp(nums): n len(nums) # 1. 初始化DP数组 dp [0] * n dp[0] ... # 初始条件 # 2. 状态转移 for i in range(1, n): dp[i] ... # 根据问题定义状态转移 # 3. 返回结果 return max(dp)/min(dp)/dp[-1] # 根据问题需求6.2 二维DP模板def two_dim_dp(matrix): m, n len(matrix), len(matrix[0]) # 1. 初始化DP表 dp [[0]*n for _ in range(m)] dp[0][0] ... # 初始条件 # 2. 处理边界情况 for i in range(1, m): dp[i][0] ... for j in range(1, n): dp[0][j] ... # 3. 状态转移 for i in range(1, m): for j in range(1, n): dp[i][j] ... # 状态转移方程 # 4. 返回结果 return dp[-1][-1] # 或其他所需结果7. 线性DP的进阶应用7.1 序列比对问题在生物信息学中线性DP广泛应用于DNA序列比对def sequenceAlignment(x, y, delta): m, n len(x), len(y) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i * delta for j in range(n1): dp[0][j] j * delta for i in range(1, m1): for j in range(1, n1): match dp[i-1][j-1] (0 if x[i-1] y[j-1] else 1) insert dp[i][j-1] delta delete dp[i-1][j] delta dp[i][j] min(match, insert, delete) return dp[m][n]7.2 资源分配问题线性DP可以解决许多资源优化配置问题def resourceAllocation(costs, profits, total): n len(costs) dp [0] * (total 1) for i in range(n): for j in range(total, costs[i]-1, -1): dp[j] max(dp[j], dp[j - costs[i]] profits[i]) return dp[total]7.3 路径计数问题网格中的路径计数是线性DP的典型应用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]8. 线性DP与其他算法的结合8.1 与前缀和结合当需要频繁查询子数组信息时可以结合前缀和优化def maxSubArraySumWithPrefix(nums): n len(nums) prefix [0] * (n 1) for i in range(n): prefix[i1] prefix[i] nums[i] min_prefix prefix[0] max_sum -float(inf) for i in range(1, n1): max_sum max(max_sum, prefix[i] - min_prefix) min_prefix min(min_prefix, prefix[i]) return max_sum8.2 与双指针结合某些问题可以通过双指针减少状态转移的计算量def longestSubstringWithoutRepeating(s): last_seen {} start 0 max_len 0 for end, char in enumerate(s): if char in last_seen and last_seen[char] start: start last_seen[char] 1 last_seen[char] end max_len max(max_len, end - start 1) return max_len8.3 与贪心算法结合在某些特殊条件下DP可以退化为贪心算法def jumpGame(nums): n len(nums) farthest 0 for i in range(n): if i farthest: return False farthest max(farthest, i nums[i]) if farthest n - 1: return True return farthest n - 19. 线性DP的实战训练建议从简单问题入手先掌握斐波那契、爬楼梯等基础问题理解状态定义尝试用不同方式定义状态比较优劣手动模拟DP表在小规模输入上手动填写DP表逐步增加难度从一维DP过渡到二维DP总结常见模式如LIS模式、背包模式、编辑距离模式等参加编程竞赛在Codeforces、LeetCode等平台专项练习训练资源推荐LeetCode动态规划专题《算法导论》动态规划章节Codeforces DP标签题目AtCoder DP专项比赛10. 线性DP的扩展思考虽然线性DP是动态规划中最基础的形式但它已经能够解决许多实际问题。掌握线性DP的关键在于培养将问题分解为子问题的思维学会定义合适的状态表示识别问题中的最优子结构性质处理重叠子问题的计算在实际工程中线性DP的思想可以应用于文本差异比较资源调度优化路径规划序列分析金融模型计算理解线性DP不仅是学习更复杂动态规划问题的基础也是培养计算机思维的重要途径。通过大量练习和总结开发者可以逐渐培养出对DP问题的敏锐直觉在面对新问题时能够快速识别是否适用DP解法并设计出高效的状态转移方程。 
长河君 · 2026/10/30 5:41:52 · 阅读 1.2k 线性动态规划基础与经典问题解析
1. 线性动态规划基础概念线性动态规划Linear Dynamic Programming是动态规划问题中最基础且应用最广泛的一类问题。这类问题的特点是状态转移方程沿着线性结构如数组、序列等进行递推每个状态只与前面有限个状态相关。动态规划本质上是一种通过空间换时间的优化技术它将问题分解为相互重叠的子问题通过存储子问题的解来避免重复计算。线性DP作为动态规划的入门类型其状态转移通常呈现明显的线性特征。关键理解线性DP中的线性指的是问题结构的线性特征而非算法的时间复杂度。即使时间复杂度可能是O(n²)或更高只要状态转移沿着单一维度推进仍属于线性DP范畴。2. 线性DP的三大核心要素2.1 状态定义状态定义是DP问题求解的第一步也是最关键的一步。对于线性DP状态通常表示为dp[i]表示考虑前i个元素时的最优解dp[i][j]当需要额外维度时的状态扩展以经典的爬楼梯问题为例状态定义dp[i]表示到达第i阶楼梯的方法数边界条件dp[0] 1, dp[1] 1状态转移dp[i] dp[i-1] dp[i-2]2.2 状态转移方程状态转移方程体现了子问题之间的关系。设计时需要考虑当前状态如何从已知状态转移得到转移的条件和限制多种转移路径中的最优选择例如在最大子数组和问题中# Kadane算法 dp[i] max(nums[i], dp[i-1] nums[i]) max_sum max(dp)2.3 初始化与边界处理边界条件处理不当会导致整个DP求解失败。常见边界情况包括序列起始位置i0或i1特殊输入空序列、单元素序列非法状态的处理3. 经典线性DP问题解析3.1 最长递增子序列(LIS)问题描述给定数组nums找到最长严格递增子序列的长度。解法def lengthOfLIS(nums): dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] nums[j]: dp[i] max(dp[i], dp[j] 1) return max(dp)时间复杂度O(n²) 空间复杂度O(n)优化思路可以结合二分查找将时间复杂度优化到O(nlogn)3.2 最大子数组和问题描述找出数组中连续子数组的最大和。解法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_sum3.3 编辑距离问题描述计算将word1转换成word2所需的最少操作次数插入、删除、替换。解法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]4. 线性DP的优化技巧4.1 空间复杂度优化当状态转移只依赖有限的前几个状态时可以使用滚动数组或变量压缩空间# 斐波那契数列空间优化 def fib(n): if n 2: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b4.2 状态转移优化对于某些问题可以通过数学分析简化状态转移# 买卖股票最佳时机问题 def maxProfit(prices): min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit4.3 单调队列/栈优化当状态转移可以表示为滑动窗口最值时可以使用单调数据结构优化# 滑动窗口最大值问题 from collections import deque def maxSlidingWindow(nums, k): q deque() res [] for i, num in enumerate(nums): while q and nums[q[-1]] num: q.pop() q.append(i) if q[0] i - k: q.popleft() if i k - 1: res.append(nums[q[0]]) return res5. 线性DP的常见错误与调试技巧5.1 初始化错误典型表现数组越界访问边界条件处理不当初始值设置不合理调试方法打印DP表的初始状态验证边界条件的正确性检查数组大小是否合理5.2 状态转移错误典型表现结果比预期偏大或偏小出现不可能的解重复计算或遗漏情况调试方法打印完整的DP表检查转移条件的逻辑完备性验证转移方程的正确性5.3 空间/时间复杂度爆炸典型表现大输入时内存不足运行时间过长解决方案分析状态依赖关系尝试空间优化寻找问题特性尝试数学优化考虑是否可以转换为贪心算法6. 线性DP的解题模板6.1 一维DP模板def linear_dp(nums): n len(nums) # 1. 初始化DP数组 dp [0] * n dp[0] ... # 初始条件 # 2. 状态转移 for i in range(1, n): dp[i] ... # 根据问题定义状态转移 # 3. 返回结果 return max(dp)/min(dp)/dp[-1] # 根据问题需求6.2 二维DP模板def two_dim_dp(matrix): m, n len(matrix), len(matrix[0]) # 1. 初始化DP表 dp [[0]*n for _ in range(m)] dp[0][0] ... # 初始条件 # 2. 处理边界情况 for i in range(1, m): dp[i][0] ... for j in range(1, n): dp[0][j] ... # 3. 状态转移 for i in range(1, m): for j in range(1, n): dp[i][j] ... # 状态转移方程 # 4. 返回结果 return dp[-1][-1] # 或其他所需结果7. 线性DP的进阶应用7.1 序列比对问题在生物信息学中线性DP广泛应用于DNA序列比对def sequenceAlignment(x, y, delta): m, n len(x), len(y) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i * delta for j in range(n1): dp[0][j] j * delta for i in range(1, m1): for j in range(1, n1): match dp[i-1][j-1] (0 if x[i-1] y[j-1] else 1) insert dp[i][j-1] delta delete dp[i-1][j] delta dp[i][j] min(match, insert, delete) return dp[m][n]7.2 资源分配问题线性DP可以解决许多资源优化配置问题def resourceAllocation(costs, profits, total): n len(costs) dp [0] * (total 1) for i in range(n): for j in range(total, costs[i]-1, -1): dp[j] max(dp[j], dp[j - costs[i]] profits[i]) return dp[total]7.3 路径计数问题网格中的路径计数是线性DP的典型应用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]8. 线性DP与其他算法的结合8.1 与前缀和结合当需要频繁查询子数组信息时可以结合前缀和优化def maxSubArraySumWithPrefix(nums): n len(nums) prefix [0] * (n 1) for i in range(n): prefix[i1] prefix[i] nums[i] min_prefix prefix[0] max_sum -float(inf) for i in range(1, n1): max_sum max(max_sum, prefix[i] - min_prefix) min_prefix min(min_prefix, prefix[i]) return max_sum8.2 与双指针结合某些问题可以通过双指针减少状态转移的计算量def longestSubstringWithoutRepeating(s): last_seen {} start 0 max_len 0 for end, char in enumerate(s): if char in last_seen and last_seen[char] start: start last_seen[char] 1 last_seen[char] end max_len max(max_len, end - start 1) return max_len8.3 与贪心算法结合在某些特殊条件下DP可以退化为贪心算法def jumpGame(nums): n len(nums) farthest 0 for i in range(n): if i farthest: return False farthest max(farthest, i nums[i]) if farthest n - 1: return True return farthest n - 19. 线性DP的实战训练建议从简单问题入手先掌握斐波那契、爬楼梯等基础问题理解状态定义尝试用不同方式定义状态比较优劣手动模拟DP表在小规模输入上手动填写DP表逐步增加难度从一维DP过渡到二维DP总结常见模式如LIS模式、背包模式、编辑距离模式等参加编程竞赛在Codeforces、LeetCode等平台专项练习训练资源推荐LeetCode动态规划专题《算法导论》动态规划章节Codeforces DP标签题目AtCoder DP专项比赛10. 线性DP的扩展思考虽然线性DP是动态规划中最基础的形式但它已经能够解决许多实际问题。掌握线性DP的关键在于培养将问题分解为子问题的思维学会定义合适的状态表示识别问题中的最优子结构性质处理重叠子问题的计算在实际工程中线性DP的思想可以应用于文本差异比较资源调度优化路径规划序列分析金融模型计算理解线性DP不仅是学习更复杂动态规划问题的基础也是培养计算机思维的重要途径。通过大量练习和总结开发者可以逐渐培养出对DP问题的敏锐直觉在面对新问题时能够快速识别是否适用DP解法并设计出高效的状态转移方程。