[理工][ALGO] 動態規劃

[ting301 ( )]

請問個蠢問題

以下搜尋費波那器數列的程式

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
推 privatewind:這不會動態規劃 這只是個遞迴程式
→ privatewind:不過動態規劃確實是常用來解遞迴
推 kiwidoit:動態規劃:f[0]=0,f[1]=1,f[2]=f[0]+f[1],f[3]=f[2]+f[1].
→ kiwidoit:慢慢的往上推...就是動態規劃了...
→ doom8199:time complexity 是 Θ([(1+√5)/2]^n)