不知道大家有没有注意到有一种算法题目，题目的参数就是几个整数，然后让你求总的方案数。

实际上仅仅是求总的方案数这一点，我的第一反应就是递推，然后就尝试找递推公式。如果再加上题目的参数是几个整数，那么这个题目大概率就是递推了，我把这种题目叫做数字型递推。

题目描述

exampleinput  : n = 2output : 2note   : 有两种方法可以爬到楼顶。         1. 1 阶 + 1 阶         2. 2 阶input  : n = 3output : 3note   : 有三种方法可以爬到楼顶。         1. 1 阶 + 1 阶 + 1 阶         2. 1 阶 + 2 阶         3. 2 阶 + 1 阶

解题思路

• 列举几个简单的台阶数，做总结，可以发现爬楼梯的方案数满足斐波那契数列。如：

  • 2阶，2种
  • 3阶，3种
  • 4阶，5种
  • 5阶，8种

    思路1 动态规划

• 状态转移方程：dp[i] = dp[i-1] + dp[i-2]

• 初始，dp[1] = 1, dp[2] = 2

• 从3到n遍历结束后，返回dp[n]即是爬楼梯的方案数

• 可以维护dp数组，保留每一个n可以产生的方案数

• 也可以不维护数组，动过迭代变量保留最后的方案数

思路2 递归（会超出时间限制）

• 从动态规划变形得到的
• 递归出口：
  • n = 1，返回1
  • n = 2，返回2
• 递归过程：
  • 返回 loop(n - 1) + loop(n - 2)

思路3 数学通项公式

• 斐波那契数列的通项公式为：
  • f(n)=[((1+√5) / 2)^n^−((1−√5)/2)^n^] / √5

代码（Java）

思路1代码

public class Solution1 {    public int climbStairs(int n) {        if (n == 1){            return 1;        }        int[] dp = new int[n + 1];        dp[1] = 1;        dp[2] = 2;        for (int i = 3; i <= n; i++){            dp[i] = dp[i-1] + dp[i-2];        }        return dp[n];    }    // 不借助dp数组的写法    public int climbStairs2(int n){        int p = 0;        int q = 1;        int r = p + q;        for (int i = 2; i <= n; i++){            p = q;            q = r;            r = p + q;        }        return r;    }}

思路2代码

public class Solution2 {    public int climbStairs(int n) {        // 超出时间限制O(2^n)        if (n <= 1) {            return 1;        }        return climbStairs(n - 1) + climbStairs(n - 2);    }}

思路3代码

public class Solution3 {    public int climbStairs(int n) {        double sqrt5 = Math.sqrt(5);        double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);        return (int) Math.round(fibn / sqrt5);    }}