题目描述

解题思路

  • 确定dp数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数值是dp[i]

  • 确定递推公式

为什么这是一道非常简单的入门题目呢？
因为题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

  • dp数组如何初始化

dp[0] = 0; dp[1] = 1;

  • 确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

  • 举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：0 1 1 2 3 5 8 13 21 34 55

  1. public int fib(int n) {
  2.     // 动态规划
  3.     if (n <= 1) {
  4.         return n;
  5.     }
  7.     int[] dp = new int[2];
  8.     dp[0] = 0;
  9.     dp[1] = 1;
  10.     int sum = 0;
  11.     // 只需要维护2个数组即可
  12.     for (int i = 2; i <= n; i++) {
  13.         sum = dp[0] + dp[1];
  14.         dp[0] = dp[1];
  15.         dp[1] = sum;
  16.     }
  18.     return dp[1];   // 不能将sum作为返回值，例如n为2时就不满足
  19. }

递归法

  1. public int fib(int n) {
  2.     // 递归法
  3.     if (n < 2) {
  4.         return n;
  5.     }
  6.     return fib(n - 1) + fib(n - 2);
  7. }