Sword10- I——斐波那契数列

方法1——动态规划

• 思路：
  • 确定状态：dp为一维数组，第n个元素为dp[n]
  • 转移方程：F(N) = (F(N - 1) + F(N - 2)) % 1000000007
  • 初始状态和边界情况：F(0) = 0，F(1) = 1
  • 计算结果：dp[n]即为第n个元素
• 特殊情况与临界分析：F(0) = 0，F(1) = 1
• 终止条件：第n项时直接返回
• 步骤：
  • 当n为0、1时，需要单独处理
  • 定义dp数组，因为dp[n]存在于n+1长度的数组中
  • 定义第0项与第1项的值
  • for循环，i从2开始，但是可以等于n
    • 求出下一项的值dp[i]，需要对结果取模1000000007
  • 返回dp[n]即为结果值

    public int fib(int n) {
        // n为0时，返回0
        if (n == 0) {
            return 0;
        }
        // n为1时，返回1
        if (n == 1) {
            return 1;
        }
        // 定义dp数组
        int[] dp = new int[n + 1];
        // 定义第0项与第1项
        dp[0] = 0;
        dp[1] = 1;
        // for循环
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 2] + dp[i - 1]) % 1000000007;
        }
        // 返回结果dp[n]
        return dp[n];
    }

• 优化：对上述两个特殊情况做合并
  • 可以将for循环更改为从0开始
  • 当n为0时，相当于跳过for循环直接返回cur为0
  • 当n为1时，for循环执行一次，返回的cur为之前的next为1
  • 综上所述，两种特殊情况都包含在内

    public int fib(int n) {
        // 定义dp数组
        int[] dp = new int[n + 1];
        // 定义第0项与第1项
        dp[0] = 0;
        dp[1] = 1;
        // for循环
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 2] + dp[i - 1]) % 1000000007;
        }
        // 返回结果dp[n]
        return dp[n];
    }

• 优化
  • 当n较大时，dp数组前面的元素已经无用还占据空间
  • 因此可以仅用几个变量来代替dp数组

    public int fib(int n) {
        // 定义第0项和第1项
        int cur = 0, next = 1, tmp = 0;
        // for循环
        for (int i = 0; i < n; i++) {
            // 求出下一项的值
            tmp = (cur + next) % 1000000007;
            // cur赋给pre
            cur = next;
            // tmp赋给cur
            next = tmp;
        }
        // 返回cur
        return cur;
    }