java 动态规划（斐波那契数列）

悠悠 2022-11-21 11:19 222阅读 0赞

--------------------

### java 动态规划（斐波那契数列） ###

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**斐波那契数列**

f(0)=0,
    f(1)=1,
    f(n)=f(n-1)+f(n-2), n>=2、n为自然数

**递归：**时间复杂度为**指数级别o(2^n)**

**递归+缓存：**斐波那契数列有重复计算，使用缓存可降低时间复杂度到**线性级别o(n)**

**动态规划：**时间复杂度为**o(n)**

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**示例**

public class MyTest3 {
    
        private static final Map<Integer,Integer> map=new HashMap<>();
    
        public static int fun(int n){
            if (n==0){
                return 0;
            }
    
            if (n==1){
                return 1;
            }
    
            return fun(n-1)+fun(n-2);
        }
    
        public static int fun2(int n){
            if (map.get(n)!=null){
                return map.get(n);
            }
    
            if (n==0){
                return 0;
            }
    
            if (n==1){
                return 1;
            }
    
            int result=fun(n-1)+fun(n-2);
            map.put(n,result);
    
            return result;
        }
    
        public static int fun3(int n){
            int[] a=new int[n+1];
            a[0]=0;
            a[1]=1;
    
            for (int i=2;i<=n;i++){
                a[i]=a[i-1]+a[i-2];
            }
    
            return a[n];
        }
    
        public static void main(String[] args){
            System.out.println("递归求解：fun(40)="+fun(40));
            System.out.println("递归缓存求解：fun(40)="+fun2(40));
            System.out.println("动态规划求解：fun3(40)="+fun3(40));
        }
    }

**控制台输出**

递归求解：fun(40)=102334155
    递归缓存求解：fun(40)=102334155
    动态规划求解：fun3(40)=102334155