动态规划斐波那契数列

Question

我正在学习动态规划在斐波那契数列中的应用并有一个问题。以下是参考代码：

import java.math.BigInteger;
import java.util.Arrays;

public class FibonacciNumbersB {

    static BigInteger[] dp = new BigInteger[10000];

    public static void main(String[] args) {
        Arrays.fill(dp, BigInteger.ZERO);
        dp[0] = BigInteger.ONE;
        dp[1] = BigInteger.ONE;

        for(int i = 4; i < 9999; i++)
            System.out.println(fibRecurse(i).toString());
    }

    public static BigInteger fibRecurse(int N) {
        for(int i = 2; i < N; i++) {
            // For numerous calls to this function, this will save as it goes
            if(dp[i].equals(BigInteger.ZERO))
                dp[i] = dp[i - 1].add(dp[i - 2]);
        }

        return dp[N - 1];
    }
}

我在 fibRecurse 方法中有一个语句检查 dp[i] 是否等于 0（尽管 fibRecurse 不是递归的）。

检查 dp[i] 是否已经计算或让 dp[i] 等于前两个元素的总和更有效？

Answer 1

import java.math.BigInteger;
import java.util.Arrays;

public class FibonacciNumbersB {

    static BigInteger[] dp = new BigInteger[10000];

    public static void main(String[] args) {
        dp[0] = BigInteger.ONE;
        dp[1] = BigInteger.ONE;
        int N = 9999;
         fibRecurse(N);
        for(int i = 0; i < N; i++)
            System.out.println(dp[i].toString()) ;
    }

    public static void fibRecurse(int N) {
        for(int i = 2; i < N; i++) {

                dp[i] = dp[i - 1].add(dp[i - 2]);
        }
    }
}

Answer 2

在执行此 memoization 时，我更喜欢 Map<Integer, BigInteger> 而不是使用固定的 BigInteger[]。请注意，您当前的方法是不是递归。 Map 可以像

一样声明和初始化

static Map<Integer, BigInteger> memo = new HashMap<>();
static {
    memo.put(0, BigInteger.ONE);
    memo.put(1, BigInteger.ONE);
}

然后检查当前 n 是否存在于 memo 中（如果是，return 它） - 否则，计算机并存储它。喜欢，

public static BigInteger fibRecurse(int n) {
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    BigInteger v = fibRecurse(n - 1).add(fibRecurse(n - 2));
    memo.put(n, v);
    return v;
}

没有 memoization 的版本会简单地省略 memo like

public static BigInteger fibRecurseSlow(int n) {
    if (n == 0 || n == 1) return BigInteger.ONE;
    BigInteger v = fibRecurse(n - 1).add(fibRecurse(n - 2));
    return v;
}

我认为您可以从我选择的方法名称中推断，哪个更慢。

Answer 3

寻找斐波那契数列的代码可以写成easily.Let寻找斐波那契数列的考虑递归代码。

import java.util.Scanner;

class fac{
  public static void main(String a[]){

    Scanner sc=new Scanner(System.in);
    System.out.print("Enter Your number :");
    int n=sc.nextInt();

    System.out.print(fibonacci(n));
}   

public static int fibonacci(int x){
    if(x<2){
        return 1;
    }
    else{
        return (fibonacci(x-1)+fibonacci(x-2));
    }
}

}

在这个阶段，有很多相同的子问题正在重新计算，again.So在这种情况下，对于大输入，时间复杂度达到了高度。由于这个原因，出现了动态规划技术......在动态规划中，额外的 table('lookUp' table) 被维护用于存储先前计算的子问题的值。在计算下一个子问题的值之前，检查创建的 table('lookUp' table) 中特定子问题的答案是否可用。如果它在 'lookUp table' 中，则获取回答特定的子问题。如果不在 'lookUp ' table 中，则计算特定问题的值并存储 'lookUp ' table。这就是动态规划的含义 technique.There 有两种执行此技术的方法。

1.Memoization - 记忆是自上而下计算子问题值的技术 manner.Let 考虑斐波那契数列的代码。

 import java.util.Scanner;

 class fab{
   public static void main(String a[]){

    Scanner sc=new Scanner(System.in);
    System.out.print("Enter Your number :");
    int n=sc.nextInt();

    int[] lookUp=new int[n];        
    int i;

    for(i=0;i<n;i++){
        lookUp[i]=-1;
    }
    fibonachi(n);   
}
public static void fibonachi(int x){
    if(lookUp[x]==-1){
        if(x<=1){
            lookUp[x]=x;
        }
        else{
            lookUp[x]=fibonachi(x-1)+fibonachi(x-2);
        }
    }
    System.out.print(lookUp[x]);
}

}

2.Tabulation - 此计算从下到上 manner.At 首先考虑基本情况并执行。然后使用前面的 cases.Les 考虑使用制表技术的斐波那契数列代码执行后续步骤。

import java.util.Scanner;

class fac{
  public static void main(String a[]){

    Scanner sc=new Scanner(System.in);
    System.out.print("Enter Your number :");
    int n=sc.nextInt();

    int[] lookUp=new int[n];        
    int i;

    lookUp[0]=1; // store base case values in the 'lookUp' table
    lookUp[1]=1;

    for(i=2;i<n;i++){
        lookUp[i]=lookUp[i-1]+lookUp[i-2];
    }
    System.out.print(lookUp[n-1]);
  }

}

在这种情况下，基本案例值存储在 first.then 使用以前的值计算下一个值..在表格中必须计算所有值，因为新值使用以前的值计算..所以记忆优于tabulation.That的全部。我希望，你能得到idea.Thank你！

动态规划斐波那契数列

Dynamic Programming Fibonacci Sequence

java

dynamic-programming

fibonacci