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