爬楼梯 (0070_climbing_stairs)

标签: dynamic_programming · 难度: EASY

输入

n: 5
DP 表:
01
11
2
3
4
5

执行过程

Step 1 · dp_init
创建 DP 表格：dp[0] 到 dp[5]，共 6 格。dp[0]=1（地面，0 级台阶有 1 种走法：不走），dp[1]=1（走 1 步到第 1 级）。

before

n=5 dp[0]=1 dp[1]=1

after

高亮: {"objects": ["dp:table"], "indices": {"dp:table": [0, 1]}}
💡 基础情况直接写好：0 级有 1 种方法（不动），1 级有 1 种方法（走 1 步）。
🧠 把 DP 表格想象成一排格子，每个格子里写着'走到这一级台阶有几种方法'。
Step 2 · dp_read
读取 dp[0]=1（2 步前）和 dp[1]=1（1 步前）

before

i=2 dp[i-2]=1 dp[i-1]=1

after

高亮: {"objects": ["dp:table"], "indices": {"dp:table": [0, 1]}}
💡 你要走到第 i 级，要么从 i-1 走 1 步上来，要么从 i-2 走 2 步上来。所以需要这两格的数据。
Step 3 · transition_considered
计算 dp[2] = dp[1] + dp[0] = 1 + 1 = 2

before

dp[i-2]=1 dp[i-1]=1 dp[i]=2

after

dp[i]=2
高亮: {"objects": ["dp:table"], "indices": {"dp:table": [0, 1, 2]}}
💡 到第 2 级的方法 = 到第 1 级的方法（再走 1 步）+ 到第 0 级的方法（再走 2 步）。
Step 4 · dp_write
写入 dp[2] = 2

before

dp[i]=2

after

dp[i]=2
高亮: {"objects": ["dp:table"], "indices": {"dp:table": [2]}}
💡 把计算结果记下来。后面算 dp[i+1] 和 dp[i+2] 时会用到这个值。
Step 5 · dp_read
读取 dp[1]=1（2 步前）和 dp[2]=2（1 步前）

before

i=3 dp[i-2]=1 dp[i-1]=2

after

高亮: {"objects": ["dp:table"], "indices": {"dp:table": [1, 2]}}
💡 你要走到第 i 级，要么从 i-1 走 1 步上来，要么从 i-2 走 2 步上来。所以需要这两格的数据。
Step 6 · transition_considered
计算 dp[3] = dp[2] + dp[1] = 2 + 1 = 3

before

dp[i-2]=1 dp[i-1]=2 dp[i]=3

after

dp[i]=3
高亮: {"objects": ["dp:table"], "indices": {"dp:table": [1, 2, 3]}}
💡 到第 3 级的方法 = 到第 2 级的方法（再走 1 步）+ 到第 1 级的方法（再走 2 步）。
Step 7 · dp_write
写入 dp[3] = 3

before

dp[i]=3

after

dp[i]=3
高亮: {"objects": ["dp:table"], "indices": {"dp:table": [3]}}
💡 把计算结果记下来。后面算 dp[i+1] 和 dp[i+2] 时会用到这个值。
Step 8 · dp_read
读取 dp[2]=2（2 步前）和 dp[3]=3（1 步前）

before

i=4 dp[i-2]=2 dp[i-1]=3

after

高亮: {"objects": ["dp:table"], "indices": {"dp:table": [2, 3]}}
💡 你要走到第 i 级，要么从 i-1 走 1 步上来，要么从 i-2 走 2 步上来。所以需要这两格的数据。
Step 9 · transition_considered
计算 dp[4] = dp[3] + dp[2] = 3 + 2 = 5

before

dp[i-2]=2 dp[i-1]=3 dp[i]=5

after

dp[i]=5
高亮: {"objects": ["dp:table"], "indices": {"dp:table": [2, 3, 4]}}
💡 到第 4 级的方法 = 到第 3 级的方法（再走 1 步）+ 到第 2 级的方法（再走 2 步）。
Step 10 · dp_write
写入 dp[4] = 5

before

dp[i]=5

after

dp[i]=5
高亮: {"objects": ["dp:table"], "indices": {"dp:table": [4]}}
💡 把计算结果记下来。后面算 dp[i+1] 和 dp[i+2] 时会用到这个值。
Step 11 · dp_read
读取 dp[3]=3（2 步前）和 dp[4]=5（1 步前）

before

i=5 dp[i-2]=3 dp[i-1]=5

after

高亮: {"objects": ["dp:table"], "indices": {"dp:table": [3, 4]}}
💡 你要走到第 i 级，要么从 i-1 走 1 步上来，要么从 i-2 走 2 步上来。所以需要这两格的数据。
Step 12 · transition_considered
计算 dp[5] = dp[4] + dp[3] = 5 + 3 = 8

before

dp[i-2]=3 dp[i-1]=5 dp[i]=8

after

dp[i]=8
高亮: {"objects": ["dp:table"], "indices": {"dp:table": [3, 4, 5]}}
💡 到第 5 级的方法 = 到第 4 级的方法（再走 1 步）+ 到第 3 级的方法（再走 2 步）。
Step 13 · dp_write
写入 dp[5] = 8

before

dp[i]=8

after

dp[i]=8
高亮: {"objects": ["dp:table"], "indices": {"dp:table": [5]}}
💡 把计算结果记下来。后面算 dp[i+1] 和 dp[i+2] 时会用到这个值。
Step 14 · return
DP 表格填充完毕。最终答案 dp[5] = 8

before

after

result=8
🧠 整个表格填满后，最后一个格子就是答案。