动态规划入门｜斐波那契、爬楼梯、打家劫舍

前言动态规划是算法笔试重难点，题型灵活但套路统一，掌握状态定义 + 状态转移方程就能通解入门题型。本篇整理最基础必刷 DP 真题，从原理到代码一站式吃透，轻松拿下入门动态规划考题。一、动态规划核心五步法确定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 b2. 爬楼梯（超高频）题意：一次爬 1 阶或 2 阶，爬到 n 阶共有多少种方法