[理工] [ALGO] 動態規劃

看板Grad-ProbAsk作者 ( )時間14年前 (2011/11/02 13:17), 編輯推噓2(2推 0噓 3→)
留言5則, 3人參與, 最新討論串1/1
請問個蠢問題 以下搜尋費波那器數列的程式 fib(int n) { if(n==0 || n==1) return 1 else return fib(n-1)+(n-2) } 這是屬於動態規劃嗎 其複雜度為O(n)? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.21.191
推
11/02 13:46, , 1F
這不會動態規劃 這只是個遞迴程式
11/02 13:46, 1F
→
11/02 13:48, , 2F
不過動態規劃確實是常用來解遞迴
11/02 13:48, 2F
推
11/02 14:09, , 3F
動態規劃:f[0]=0,f[1]=1,f[2]=f[0]+f[1],f[3]=f[2]+f[1].
11/02 14:09, 3F
→
11/02 14:10, , 4F
慢慢的往上推...就是動態規劃了...
11/02 14:10, 4F
→
11/02 15:04, , 5F
time complexity 是 Θ([(1+√5)/2]^n)
11/02 15:04, 5F
‣ 更多 ting301 的文章
文章代碼(AID): #1EiD9UEh (Grad-ProbAsk)