1. 线性动态规划基础概念解析

线性动态规划（Linear Dynamic Programming）是算法设计中最为基础且重要的技术之一。不同于传统递归的暴力解法，动态规划通过存储子问题的解来避免重复计算，将指数级时间复杂度优化至多项式级别。其核心特征体现在"线性"结构上——问题的状态转移沿着单一维度进行，形成清晰的递推关系链。

典型线性DP问题具有三个关键要素：

1. 状态定义：用dp[i]表示第i个阶段的最优解
2. 转移方程：明确dp[i]与dp[i-1], dp[i-2]等前驱状态的关系
3. 边界条件：确定初始状态如dp[0]、dp[1]的取值

以经典的斐波那契数列为例：

def fib(n): dp = [0] * (n+1) dp[0], dp[1] = 0, 1 # 边界条件 for i in range(2, n+1): 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 a

2. 线性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_sum

2.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]*(W+1) for _ in range(n+1)] for i in range(1, n+1): for w in range(1, W+1): 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, n+1): a, b = b, a + b return b

3.2 状态机模型

某些问题需要同时维护多个状态。如股票买卖问题：

def maxProfit(prices): n = len(prices) dp = [[0]*2 for _ in range(n+1)] dp[0][1] = -float('inf') for i in range(1, n+1): 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_sum

4. 线性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] 最大值为6

5. 线性DP的进阶应用

5.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] = 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]*(n+1) for _ in range(m+1)] dp[0][0] = True for j in range(1, n+1): if p[j-1] == '*': dp[0][j] = dp[0][j-2] for i in range(1, m+1): for j in range(1, n+1): 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 res

6. 线性DP的常见误区与修正

6.1 错误的状态定义

典型错误：在LIS问题中试图用dp[i]表示以i结尾的子序列数。正确应表示长度。

6.2 遗漏边界条件

如斐波那契中忘记处理n=0的情况，或路径问题中未初始化第一行/列。

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的扩展训练建议

1. 从经典问题入手：斐波那契→爬楼梯→打家劫舍→股票买卖
2. 循序渐进增加维度：一维→二维→带状态的多维
3. 对比记忆化搜索与递推写法
4. 尝试空间优化版本
5. 参加编程竞赛（如LeetCode周赛）实战演练

推荐训练题库：

• LeetCode动态规划专题（按难度排序）
• 《算法导论》第15章动态规划
• 《算法竞赛入门经典》第9章动态规划

在实际编码中，建议先用记忆化搜索（递归+缓存）思考问题，再转化为递推形式。例如斐波那契的记忆化版本：

from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n < 2: return n return fib(n-1) + fib(n-2)

这种写法更直观，能帮助理解状态转移关系，再优化为迭代版本。