##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Walkthrough and analysis
Trace n = 5.
dp[1] = 1 (one way: single step) dp[2] = 2 (two ways: 1+1 or 2) dp[3] = dp[2] + dp[1] = 2 + 1 = 3 dp[4] = dp[3] + dp[2] = 3 + 2 = 5 dp[5] = dp[4] + dp[3] = 5 + 3 = 8
Answer: ways to climb stairs.
Verify: 11111, 1112, 1121, 1211, 2111, 122, 212, 221. That's .
time iterating once. space keeping only two previous values.
