文章目錄

• 題目描述
• 思路 & 代碼
• • • 遞歸
    • 動態(tài)規(guī)劃
    • 二刷

題目描述

• 呃～說來尷尬，在簡單題栽跟頭了= = （超時）
• 一般來說，這玩意是遞歸教學(xué)題了。但實際上會有很多重復(fù)的冗余步驟，實際上用動態(tài)規(guī)劃效率會更高
  

思路 & 代碼

遞歸

class Solution {public int fib(int n) {if(n == 0 || n == 1){return n;}return (fib(n - 1) + fib(n - 2)) % 1000000007;} }

動態(tài)規(guī)劃

• O(n) & O(n)

class Solution {int[] ans = new int[101];public int fib(int n) {// O(n) & O(n) 的動態(tài)規(guī)劃ans[0] = 0;ans[1] = 1;for(int i = 2; i <= n; i++){ans[i] = ans[i - 1] + ans[i - 2];ans[i] %= 1000000007;}return ans[n];} }

• O(n) & O(1) ，因為這道題實際上只要記錄當(dāng)前兩個元素的狀態(tài)即可，因此實際上可以用兩個變量起到整個數(shù)組的作用。

class Solution {public int fib(int n) {// O(n) & O(1) 的動態(tài)規(guī)劃int a = 0;int b = 1;int sum = 0;for(int i = 1; i <= n; i++){sum = (a + b) % 1000000007;a = b;b = sum;}return a;} }

二刷

• 邊界和返回值還是值得注意的

class Solution {public int fib(int n) {int pre = 0, now = 1, next = 0;for(int i = 1; i <= n; i++) {next = (pre + now) % 1000000007;pre = now;now = next;}return pre;} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】剑指 Offer 10-I. 斐波那契数列 （Java、递归、动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。