Java 数据结构 - 斐波那契数列

动态规划方法类似于分治法，将问题分解成越来越小的子问题。但与分治法不同，这些子问题不是独立解决的。相反，这些较小子问题的结果会被记住并用于类似或重叠的子问题。

动态规划用于存在可以分解成类似子问题的问题，以便可以重用其结果。通常，这些算法用于优化。在解决手头的子问题之前，动态算法会尝试检查先前解决的子问题的结果。子问题的解被组合起来以获得最佳解。

所以我们可以说 -

• 问题应该能够分解成较小的重叠子问题。

• 可以使用较小子问题的最优解来获得最优解。

• 动态算法使用记忆化。

比较

与解决局部优化的贪心算法相比，动态算法的目标是对问题进行全局优化。

与将解组合起来以获得整体解的分治算法相比，动态算法使用较小子问题的输出，然后尝试优化较大的子问题。动态算法使用记忆化来记住已解决子问题的输出。

动态规划可以自顶向下和自底向上两种方式使用。当然，在大多数情况下，从之前的解决方案输出中引用比重新计算在 CPU 周期方面更便宜。

Java 中的斐波那契数列

以下是使用动态规划技术在 Java 中解决斐波那契数列的方案。

示例

import java.util.Scanner;

public class Fibonacci {
   public static int fibonacci(int num) {
      int fib[] = new int[num + 1];
      fib[0] = 0;
      fib[1] = 1;
      
      for (int i = 2; i < num + 1; i++) {
         fib[i] = fib[i - 1] + fib[i - 2];
      }
      return fib[num];
   }
   public static void main(String[] args) {
	   Scanner sc = new Scanner(System.in);
      System.out.println("Enter a number :");
      int num = sc.nextInt();
      
      for (int i = 1; i <= num; i++) {
         System.out.print(" "+fibonacci(i));
      }
   }
}

输出

1 1 2 3 5 8 13 21 34 55 89 144