剑指offer - 变态跳台阶(Java实现)

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

  由跳台阶中dp思想的描述，我们可以得到递推式，f[n] = f[n - 1] + f[n - 2] + ... + f[0]；

跳台阶：https://blog.nowcoder.net/n/2723e2e6740c40219ebbb06fd1410265

  思路一：两层循环暴力求解即可。

public class Solution {
    public int JumpFloorII(int target) {
        int[] fib = new int[target + 1];
        fib[0] = 1; fib[1] = 1;
        for(int i = 2; i <= target; ++ i) {
            for(int j = 0; j < i; ++ j) {
                fib[i] += fib[j];
            }
        }
        return fib[target];
    }
}

  思路二：优化，我们可以发现，每次我们加上的都是前 i - 1 项的和，也就是 i - 1 的前缀和，所以我们可以一边更新前缀和，一边更新fib。

public class Solution {
    public int JumpFloorII(int target) {
        int[] fib = new int[target + 1];
        int sum = 2;
        fib[0] = 1; fib[1] = 1; 
        for(int i = 2; i <= target; ++ i) {
            fib[i] = sum;
            sum += fib[i];
            //return fib[i];
        }
        return fib[target];
    }
}

  思路三：数学、思维。
  
  
  
  

public class Solution {
    public int JumpFloorII(int target) {
        return target == 0 ? 1 : 1 << (target - 1);
    }
}