上台阶问题

有n阶台阶（n>0），小明一次可以上一步，或者两步，请问小明有多少种上台阶的方案？

设小明有种上台阶方案，当n>2时，容易得到

下面给出四种编程思路

递归

由迭代公式很容易得到想到递归过程，代码如下

int getStep(int n) {
    if (n==1) return 1;
    if (n==2) return 2;
    return getStep(n-1) + getStep(n-2);
}

动态规划

动态规划就是将计算的中间过程保存到临时变量dp中，代码如下

int[] dp;
void setDp(int n) {
    if (dp[n]==0){
        dp[n] = getStep(n);
    }
}
int getStep(int n) {
    if (n==1) return 1;
    if (n==2) return 2;
    setDp(n-1);
    setDp(n-2);
    return dp[n-1]+dp[n-2];
}
int getStepDp(int n) {
    dp = new int[n];
    return getStep(n);
}

排列组合

该问题可以转化为

所有解的全排列问题，具体代码如下

    // 该方法有数据溢出问题，需要通过分解质因数优化,在Java上调试当n>26
    int getAC(int m, int n) {
        int result = 1;
        if (n>m) {
            int temp = n;
            n = m;
            m = temp;
        }
        for (int i = m+1; i < m+n+1; i++) {
            result *= i;
        }
        for (int i = 2; i <= n; i++) {
            result /= i;
        }
        return result;
    }

    int getStepAC(int n) {
        int result = 0;
        for (int i = 0; i <= n/2; i++) {
            result += getAC(i, n-2*i);
        }
        return result;
    }

数学求解

推导数列公式得

代码如下

    int getStepMath(int n) {
        double sqrt5 = Math.sqrt(5);
        double left = (1.0 + sqrt5)/2.0;
        double right = (1.0- sqrt5)/2.0;
        return (int)Math.round(Math.pow(left, n+1));
    }