前言
动态规划是算法笔试重难点，题型灵活但套路统一，掌握状态定义 + 状态转移方程就能通解入门题型。本篇整理最基础必刷 DP 真题，从原理到代码一站式吃透，轻松拿下入门动态规划考题。
一、动态规划核心五步法
二、DP 三大核心思想
- 重叠子问题：重复计算的子问题只算一次
- 最优子结构：大问题最优解由小问题最优解推出
- 无后效性：当前状态只依赖过往状态，不受未来影响
三、入门经典手撕题
1. 斐波那契数列
题意：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)
# 基础DP
def fib(n):
if n <= 1:
return n
dp = [0]*(n+1)
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# 空间优化版
def fib_opt(n):
if n <= 1:
return n
a,b = 0,1
for _ in range(2,n+1):
a,b = b,a+b
return b
2. 爬楼梯（超高频）
题意：一次爬 1 阶或 2 阶，爬到 n 阶共有多少种方法
