1. 项目概述
OJ（Online Judge）学习笔记系列是我在算法竞赛训练过程中记录的实战心得。Day2的笔记主要聚焦于动态规划（DP）基础题型的解题思路与代码实现优化。作为算法竞赛中最核心的解题方法之一，动态规划在各大OJ平台（如LeetCode、Codeforces）的题目中占比超过30%，但也是新手最容易产生挫败感的知识点。
我在ACM集训队担任助教期间发现，约70%的学员在初次接触动态规划时会陷入"能看懂题解但自己写不出"的困境。这份笔记不同于教科书式的理论讲解，而是通过三道经典入门题（爬楼梯、最大子序和、打家劫舍）的逐行代码分析，揭示状态转移方程的构建技巧。特别适合已经了解DP概念但缺乏实战经验的学习者。
2. 核心题型解析
2.1 爬楼梯问题（LeetCode 70）
题目描述：需要爬n阶楼梯，每次可以爬1或2阶，求有多少种不同的方法可以爬到楼顶。
暴力递归解法的问题
python复制def climbStairs(n):
if n <= 2:
return n
return climbStairs(n-1) + climbStairs(n-2)
这种解法时间复杂度为O(2^n)，当n=40时计算量已达万亿级别。我在本地测试时发现n=38就需要超过10秒才能得出结果。
动态规划优化方案
python复制def climbStairs(n):
if n <= 2:
return n
dp = [0]*(n+1)
dp[1], dp[2] = 1, 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
关键技巧：dp数组的初始化需要根据边界条件仔细设置。有学员经常错误地将dp[0]初始化为1，导致后续计算出现偏差。
空间复杂度可进一步优化到O(1)：
python复制def climbStairs(n):
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n+1):
a, b = b, a+b
return b
2.2 最大子序和（LeetCode 53）
题目描述：给定整数数组nums，找出具有最大和的连续子数组。
常见误区分析
很多初学者会尝试双重循环暴力求解，时间复杂度O(n^2)。当数组长度达到10^5时（如Codeforces竞赛常见数据规模），这种解法必然超时。
动态规划解法
python复制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)
实战心得：这里的dp[i]表示以nums[i]结尾的最大子序和，而非前i个元素的最大和。这个定义差异是解题的关键，也是我当初理解时的障碍点。
优化空间版本：
python复制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
3. 状态转移方程构建技巧
3.1 问题分解三步骤
-
定义状态：明确dp数组每个下标的含义
- 爬楼梯：dp[i]表示到第i阶的方法数
- 打家劫舍：dp[i]表示前i间房能偷到的最大金额
-
确定转移方程：找出状态间的关系
- 斐波那契关系：dp[i] = dp[i-1] + dp[i-2]
- 选择关系：dp[i] = max(dp[i-1], dp[i-2]+nums[i])
-
设置初始条件：通常需要手动设置前2-3项的值
3.2 滚动数组优化原理
当状态转移只依赖前几个状态时，可以用有限变量代替整个dp数组。以打家劫舍问题为例：
原始dp数组：
python复制dp = [0]*n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
优化后：
python复制prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, n):
curr = max(prev1, prev2+nums[i])
prev2, prev1 = prev1, curr
4. 常见错误与调试方法
4.1 数组越界问题
在初始化dp数组时，必须考虑n=0或n=1的特殊情况。例如打家劫舍问题：
错误写法：
python复制dp = [0]*n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1]) # 当n=1时会报错
正确写法：
python复制if n == 0:
return 0
if n == 1:
return nums[0]
4.2 状态转移方向错误
有些问题需要正序推导（如爬楼梯），有些则需要倒序处理（如背包问题）。我曾在一个二维DP问题中因为遍历方向错误导致结果异常：
错误示例：
python复制for i in range(n):
for j in range(m):
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # 未处理i=0或j=0的边界
正确写法：
python复制# 先初始化第一行和第一列
for i in range(1, n):
for j in range(1, m):
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
4.3 记忆化搜索实现技巧
对于树形DP等问题，递归+记忆化可能比迭代更直观：
python复制from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(node):
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
return max(left, right) + node.val
注意事项：Python的递归深度默认限制为1000，对于深度较大的树需要先调用sys.setrecursionlimit()调整
5. 训练建议与资源推荐
5.1 刻意训练计划
-
基础阶段（2周）：
- 每日3道经典DP问题（推荐LeetCode精选50题）
- 重点练习：斐波那契变种、路径问题、简单背包问题
-
提高阶段（1个月）：
- 接触树形DP、状态压缩DP等高级题型
- 参加每周Codeforces Div2比赛，重点分析C题通常的DP考点
-
竞赛冲刺：
- 研究ICPC/CCPC历年真题的DP解法
- 整理常见优化技巧：斜率优化、四边形不等式等
5.2 实用调试工具
-
可视化调试：
- 使用Python Tutor观察dp数组变化
- 手动画出状态转移图（特别是二维DP问题）
-
对拍测试：
python复制def brute_force(n): # 实现暴力解法 pass for _ in range(100): n = random.randint(1, 20) assert dp_solution(n) == brute_force(n) -
性能分析：
python复制import timeit print(timeit.timeit(lambda: climbStairs(40), number=10))
5.3 推荐学习资源
- 《算法导论》第15章 - 动态规划原理
- Codeforces动态规划专题（标签：dp）
- 背包九讲（特别适合NOIP/ICPC选手）
- LeetCode动态规划学习卡片
在后续训练中，建议建立自己的错题本，记录每道DP问题的三个关键点：状态定义、转移方程、初始化条件。我个人的经验是，当累计解决50道不同变种的DP问题后，对新题的思路形成速度会有质的提升。