[数据结构与算法]牛客网剑指offer=＞递归

JZ8 跳台阶

https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=13&&tqId=11161&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution {
    /*
    动态规划f(n) = f(n-1)+f(n-2);
    只要求第target，可以省去dp[n]的空间
    */
    public int jumpFloor(int target) {
        int a=1,b=1;
        for(int i=2;i<=target;i++){
            a = a + b;
            b = a - b;
        }
        return a;
    }
}

JZ9 跳台阶扩展问题

https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&&tqId=11162&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution {
        /*
        f(n) = f(n-1)+f(n-2)+f(n-3)+...+f(1);
        f(n-1) = f(n-2)+f(n-3)+...+f(1);
        两个式子相减得到
        f(n) = 2f(n-1);
        f(1) = 1;
        所以f(n) = pow(2,n-1)
        */
    public int jumpFloorII(int target) {
        return target<=0?0:1<<(target-1);
    }
}