算法题7.变态跳台阶

题目描述:

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

读完题就感觉可以用动态规划的思想解决问题：因为一次可以跳1~n阶，所以f(n)可以依次从f(n-1)、f(n-2)...f(n-n)这里再跳一次到达n阶台阶。

先附上自己的解决方法：

public class Solution{


    /**
     * 动态规划
     * 解题思路：
     * 将函数名简化为f，便于讲解。
     * 因为一次可以跳1-n阶，所以f(n)可以依次从f(n-1)、f(n-2)...f(n-n)这里再跳一次到达n阶台阶，
     * 例如：n=3,则可以从第2阶（3-1）跳1阶到达，可以从第1阶（3-2）跳2阶到达，还可以(3-3)直接跳3阶到达。
     * 由此得出结论：
     * f(0) = 1，
     * f(n) = f(n-1) + f(n-2) + ... + f(n-n)
     *      = f(0) + f(1) + ...+ f(n-1)
     */
    public int JumpFloorII(int target) {
        //申请数组存储
        int[] results = new int[target + 1];
        //f(0) = 1
        results[0] = 1;
        //从f(1)开始计算，直到计算到f(target)目标为止
        for (int i = 1; i <= target; i++) {
            for (int j = i - 1; j >= 0; j--) {
                results[i] += results[j];
            }
        }
        return results[target];
    }

}

进阶：
虽然解决了问题，但是很明显能感觉到这个方法太过于笨拙，嵌套循环，于是在评论区中找到的优化方案：在上面我们得出结论f(n) = f(0) + f(1) + ...+ f(n-2) + f(n-1)，由同样的方法可以得出f(n-1) = f(0) + f(1) + ... + f(n-2)，于是我们可以将f(n)化简f(n) = 2 * f(n-1)。

/**
 * f(n-1) = f(n-1 -1) + f(n-1 -2) + .... + f(n-1 -(n-1))
 * = f(n-2) + f(n-3) + .... + f(n-n)
 * = f(0) + f(1) + ... + f(n-2)，
 * f(n) = f(n-1) + f(n-2) + ... + f(n-n)
 * = f(0) + f(1) + ...+  f(n-2) + f(n-1)
 * <p>
 * 所以，f(n) = 2 * f(n-1)
 */
public int JumpFloorII(int target) {

    if (target <= 0) {
        //非法参数情况
        return -1;
    } else if (target == 1) {
        //结束条件，f(1) = 1
        return 1;
    } else {
        //递归
        return 2 * JumpFloorII1(target - 1);
    }
}

再进阶：
其实通过测试用例，你可能已经发现了。同样的，使用上面得到的结论继续推：f(1) = 1、f(2)= 2 * f(1) = 2 * 1、f(3) = 2 * f(2) = 2 * 2 * 1、...、f(n) = 2 * f(n-1) = 2 * 2 * f(n-2) = ... = 2^(n-1)。

/***
 * f(1) = 1
 * f(2)= 2 * f(1) = 2 * 1
 * f(3) = 2 * f(2) = 2 * 2 * 1
 * f(n) = 2 * f(n-1) = 2 * 2 * f(n-2) = ... = 2^(n-1)
 */
public int JumpFloorII(int target) {
    return (int) Math.pow(2, target - 1);
}

再再进阶
通常我们为了提高效率，会采用到移位操作，在这里同样可以使用，简直高大上啊，一行代码解决问题：

/**
 * 移位操作
 */
public static int JumpFloorII1(int target) {
    return 1 << (target - 1);
}