Offer0009

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

思路： 找规律！！！

• 规律一 : 方案数 = 2^(n-1)

  —快速幂计算—

      public int JumpFloorII(int target) {
          if (target <= 1) return 1;
          int res = fastpow(2, target-1);
          return res;
      }
    
      public int fastpow(int a, int b) {
          int res = 1;
          if (b <= 0) return res;
          while (b > 0) {
              if (b % 2 == 1) {
                  res *= a;
              }
              a *= a;
              b >>= 1;
          }
          return res;
      }
  

  
  

• 规律二 :
  | 1 (n=0)
  f(n) = | 1 (n=1)
  | 2*f(n-1) (n>=2)

Offer0010

题目描述： 我们可以用2×1的小矩形横着或者竖着去覆盖更大的矩形。 请问用n个2×1的小矩形无重叠地覆盖一个2×n的大矩形，总共有多少种方法？

思路：

1、target<=0，1
2、target==1，1
3、target==2，2
4、target==n ->
木块有两种变换的形态->2×1 和 (1×2)×2
—–当使用2×1时
1 0 0 0 有f(target-1)种方案
1 0 0 0
—–当使用(1×2)×2时
11 0 0 有f(target-2)种方案
11 0 0
—–> f(target) = f(target-1) + f(target-2)
——–斐波那契数列规律！！

代码:

斐波那契数列其他的实现方法：快戳我

 public int RectCover(int target) {
        if (target <= 0) return 0;
        if (target == 1) return 1;
        if (target == 2) return 2;
        int[] fib = new int[target + 1];
        fib[0] = 0;
        fib[1] = 1;
        fib[2] = 2;
        for (int i = 3; i <= target; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        return fib[target];
    }