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

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

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

*********************

斐波那契数列

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

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

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

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

*********************

示例

  1. public class MyTest3 {
  3.     private static final Map<Integer,Integer> map=new HashMap<>();
  5.     public static int fun(int n){
  6.         if (n==0){
  7.             return 0;
  8.         }
  10.         if (n==1){
  11.             return 1;
  12.         }
  14.         return fun(n-1)+fun(n-2);
  15.     }
  17.     public static int fun2(int n){
  18.         if (map.get(n)!=null){
  19.             return map.get(n);
  20.         }
  22.         if (n==0){
  23.             return 0;
  24.         }
  26.         if (n==1){
  27.             return 1;
  28.         }
  30.         int result=fun(n-1)+fun(n-2);
  31.         map.put(n,result);
  33.         return result;
  34.     }
  36.     public static int fun3(int n){
  37.         int[] a=new int[n+1];
  38.         a[0]=0;
  39.         a[1]=1;
  41.         for (int i=2;i<=n;i++){
  42.             a[i]=a[i-1]+a[i-2];
  43.         }
  45.         return a[n];
  46.     }
  48.     public static void main(String[] args){
  49.         System.out.println("递归求解：fun(40)="+fun(40));
  50.         System.out.println("递归缓存求解：fun(40)="+fun2(40));
  51.         System.out.println("动态规划求解：fun3(40)="+fun3(40));
  52.     }
  53. }

控制台输出

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

发表评论

表情：
评论列表 （有 0 条评论，328人围观）

还没有评论，来说两句吧...

相关阅读

    相关 斐波那契数列

    关于斐波那契数列的解法，本人找到了一种比较简单的方法，结果是正确的，不知道各位有没有另外更好的解法，一起探讨探讨。 import java.util.; pu

    ╰+攻爆jí腚メ╰+攻爆jí腚メ/ 0 赞/ 508 阅读