剑指offer10-1 10-2

方法1：

 1 class Solution {
 2 
 3     public int fib(int n){
 4         return fibGetN(n)%(1000000007);
 5     }
 6 
 7     public static int fibGetN(int n){
 8         if(n==0) return 0;
 9         else if(n==1) return 1;
10         else return fibGetN(n-1) + fibGetN(n-2);
11     }
12 }

需要注意数值溢出的问题。

2.青蛙跳台阶问题

 1 class Solution {
 2 
 3     public int numWays(int n) {
 4         if(n == 0) return 1;
 5         if(n < 3) return n;
 6         int cur1 = 1, cur2 = 2;
 7         for(int i = 3; i <= n; i++){
 8             int temp = cur1 + cur2;
 9             cur1 = cur2;
10             cur2 = temp%1000000007;
11         }
12         return cur2;
13     }
14 
15 
16 }

知之为知之，不知为不知