从爬楼梯问题入门动态规划

Description:
n个台阶的楼梯，一次只能爬1个台阶或者2个台阶，爬到n个台阶一共有多少种可能性？

我对这道题印象极其深刻，最早知道它是高中数学课上大象老师提出它，解题思路是：

  1. 记n个台阶的可能性是s(n),因为一次只能爬1或者2个台阶，因此上一步，只能是从第n-1爬一步，或者从第n-2爬2步
  2. 第n-1记s(n-1),第n-2记s(n-2)
  3. 于是可得出递归函数: s(n) = s(n-1) + s(n-2)

LeetCode 70: https://leetcode.com/problems/climbing-stairs/submissions/

我们以迅雷不及掩耳之响铃铛芝士提交代码：

1
2
3
4
5
6
7
8
9
10
11
var climbStairs = function(n) {
    if(n === 1) {
        return 1;
    }
   
    if(n === 2) {
        return 2;
    }
   
    return climbStairs(n - 1) + climbStairs( n - 2)
};

系统反手一个超时！
问题出现在递归函数，展开递归函数，是一个近乎完全二叉树，容易得出结论：

1
2
3
4
`s(n-2)`计算2次
`s(n-3)`计算3次
 。。。
`s(1)`计算n-1次

计算量如此，映射到实际的运行时间上：t(n) = t(n-1) + t(n-2), 实际打表显示的耗时符合这个公式。
触目惊心，额外计算了这么多次。

我们要记录这些中间计算，这样耗时就是线性的n了。
我突然明白了动态第二个核心: 缓存中间计算，大约也叫剪纸吧,因为缓存子问题结果后，就不用再重复计算子问题了。在知乎上看到一个例子：

如何像小学生解释动态规划：

  1. 在纸上写1+1+1+1+1+1+1+1.
  2. 求出答案是8
  3. 在左侧写个1+，问答案是多少？
  4. 瞬间计算出答案9，原因是记录了中间值8.

好，我们用记录中间值得思路去解决这个问题：

1
2
3
4
5
6
7
8
9
10
const stepMap = {};
var climbStairs = function(n) {
    if(n === 1) return 1;
    if(n === 2) return 2;
    
    let steps = (stepMap[n - 1] ||  climbStairs(n - 1)) + (stepMap[ n - 2] || climbStairs( n - 2));
    stepMap[n] = steps;
    
    return steps;
};

至此再也不用担心超时了。我们继续优化代码到js的最优雅解法， it’s beautiful.

1
2
3
4
var climbStairs = function(n, a=1, b=1) {
  if(n == 1) return b;
  return climbStairs(n-1,b,a+b); 
};

以上可以得出DP的解题思路：

  1. 找出状态转移公式（用递归切割子问题）
  2. 缓存中间状态值。