leeyupeng

leeyupeng@126.com

0%

递归与动态规划

发表于 更新于 分类于 ， 阅读次数： Valine：

递归与动态规划

分析

1.递归问题是否都可以使用动态规划来解决？
满足条件f(n1,n2,n3)=f(n1-k1,n2-k2,n3-k3)
0<=k1,k2,k3 是否就可以通过动态规划来解决递归问题

2.可以使用动态规划解决的问题是否都是递归类型的问题

特征

斐波那契数列(Fibonacci)

递归

超时 

1
2
3
4
5
6
7
class Solution {
public:
    int fib(int n) {
        if(n<=1){return n;}
        return (fib(n-1)+fib(n-2))%(1e9+7);
    }
};

动态规划

时间复杂度 O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int fib(int n) {
        int f1 = 0,f2 = 1;
        int f=n;
        for(int i = 2; i <= n; i++){
            f=f1+f2;
            if(f>1e9+7){f-=1e9+7;}
            f1 = f2;
            f2 = f;
        }
        return f;
    }
};