Python 算法教程（21）：动态规划基础详解
前言
动态规划（Dynamic Programming）是算法中最重要也最难的部分，本文从基础讲起。
一、核心思想
将大问题分解为重叠子问题，保存子问题的解，避免重复计算。
二、解题框架
# 1. 定义状态
dp[i] = ... # 表示什么含义
# 2. 状态转移方程
dp[i] = dp[i-1] + dp[i-2] # 如何从已知推未知
# 3. 初始化
dp[0] = base_case # 边界条件
# 4. 遍历顺序
for i in range(1, n): # 从小到大或从大到小
dp[i] = ...
# 5. 返回结果
return dp[n-1]三、经典例题：爬楼梯
def climbStairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]四、空间优化
def climbStairs_optimized(n):
if n <= 2:
return n
a, b = 1, 2
for i in range(3, n + 1):
a, b = b, a + b
return b五、复杂度
时间：O(n)，空间：O(1)（优化后）
六、LeetCode 实战
70. 爬楼梯、509. 斐波那契数
总结
掌握 DP 五步法，多刷经典题目。
下一篇：最长公共子序列
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
