假设正在爬楼梯，需要 n 阶才能到达楼顶；如果每次可以爬 1、2 或 3 个台阶，问有多少种不同的方法可以爬到楼顶？

• 第 0 阶有 1 种方法可以爬；

• 第 1 阶有 1 种；

• 第 2 阶有 2 种（1+1、2）；

• 第 3 阶有 4 种（1+1+1、2+1、3、1+2）；

• 第 4 阶有 7 种（1+1+1+1、2+2、2+1+1，3+1，1+2+1、1+1+2、1+3）；

• 第 5 阶有 13 种；

• 第 6 阶有 24 种；

• …

以上可以看作一个子问题图，即第 1 阶需要第 0 阶的解，第 2 阶需要第 0、1 阶解..；从第 3 阶开始则需要前面 3 阶（0、1、2）的解、第 4 阶也需要前面 3 阶的解；这里需要的是解，即答案，而不是实际的方案，第 3 阶有 4 种（1+1+1、2+1、3、1+2） 此处括号里的是实际的方案，可能有些问题需要这些实际的方案，但是这里的爬楼梯问题只需要的只是解，即 多少种 方案。

 def climb(n: Int): Int = {
   // 第 0 ~ 2 阶的直接返回
   if n < 3 then {
     if n == 0 || n == 1 then return 1
     return 2
   }
 ​
   // 动态规划需要创建一个容器存放处理过程的子问题解
   val dp = new Array[Int](n + 1)
   // 初始化 0 ~ 2 阶的状态，因为这些阶没有固定的规律
   dp(0) = 1
   dp(1) = 1
   dp(2) = 2
   // 状态转移，dp(i - 1) 前一阶、dp(i - 3) 前三阶
   (3 to n).foreach(i => dp(i) = dp(i - 1) + dp(i - 2) + dp(i - 3))
 ​
   dp.last
 }

dp 数组存放了每一个阶梯的方案数，但是从第 3 阶开始，只需要当前阶的前 3 阶就能计算出方案数，可以用几个临时变量代替数组，以优化空间：

 def climb(n: Int): Int = {
   if n < 3 then {
     if n == 0 || n == 1 then return 1
     return 2
   }
 ​
   // dp 表示当前阶，前 3 阶分别是 dp1, dp2, dp3
   var (dp1, dp2, dp3, dp) = (1, 1, 2, 0)
   (3 to n).foreach(_ => {
     dp = dp1 + dp2 + dp3
     dp1 = dp2
     dp2 = dp3
     dp3 = dp
   })
 ​
   dp
 }