Day3

剑指offer 10 斐波拉契数列

题目描述

滚动数组（动态规划）

解答

class Solution {
    public int fib(int n) {
        if(n<2) return n;
        int p=0,q=1,r=0;
        final int mod=1000000007;
        for(int i=2;i<n+1;i++){
            //p,q先相加得r，然后p,q后移
            r=(p+q)%mod;
            p=q;
            q=r;
        }
        return r;
    }
}

剑指offer 10 青蛙跳台阶问题

题目描述

思路（动态规划）

此类求 多少种可能性的题目一般都有递归性质，即f(n),f(n-1)…f(1)之间是有联系的。

设跳上 n 级台阶有 f(n) 种跳法。在所有的跳法中。青蛙的最后一步只有两种情况：跳上1级或者2级台阶，当为1级台阶：剩 n-1 个台阶，此情况共有f(n-1) 种跳法；当为2级台阶，剩 n-2 个台阶，此情况共有 f(n-2) 种跳法。

f(n) 为以上两种情况之和，即 f(n)=f(n-1)+f(n-2),所以为斐波拉契数列问题。

解答

class Solution {
    public int numWays(int n) {
        int p=1,q=2,sum=0;
        if(n==0) return 1;
        if(n==1) return 1;
        if(n==2) return 2;
        for(int i=3;i<=n;i++){
            sum=(p+q)%1000000007;
            p=q;
            q=sum;
        }
        return sum;
    }
}