数据结构(day11)

1 采用函数递归，在数据量比较大时会出现超时

class Solution {
    public int fib(int n) {
         if(n==0) return 0;
         if(n==1) return 1;
        return (fib(n-1)+fib(n-2))%1000000007;
    }
}

 

2 我们使用动态规划来求解，动态规划和递归算法是差不多的

递归是从顶到底的计算

动态规划是从底到顶来计算

大体意思是我们知道0 和1 然后通过0和1来计算出顶部的值

class Solution {
    public int fib(int n) {
         if(n==0) return 0;
         if(n==1) return 1;
        int[] a=new int[n+1];
        a[1]=1;
        for(int i=2;i

这个时候的时间复杂度是O(n)  

其实是还可以降低的空间复杂度的，即我们不使用数组进行存储

class Solution {
    public int fib(int n) {
         if(n==0) return 0;
         int a=0; int b=1;
        for(int i=2;i<=n;i++){
           int tem=a;
            a=b;
            b=(tem+a)%1000000007;
        }
        return b;
    }
}

这里要注意的题目是要我们每次的结果都要取模，因此我们每次都要%1000000007

青蛙跳台也跟斐波那契是一样的

n=0  返回1 

n=1 返回1

n=2 返回 2

n=3 返回3

n=4 返回 5

我们可以发现也是 2之后都是  f(n)=f(n-1)+f(n-2)

我们还是可以利用动态规划的方法来解决问题

class Solution {
    public int numWays(int n) {
        if(n==0) return 1;
        int a=1;int b=1;
        for(int i=2;i<=n;i++){
            int tem=a;
            a=b;
            b=(tem+a)%1000000007;
        }
        return b;
    }
}