數據結構

動態規劃算法

動態規劃算法

動態規劃也被稱為記憶技術。動態規劃是一種很好的方法,因為它的思想是存儲以前計算的結果,以避免再次計算。在動態規劃中,將複雜的問題分解成子部分,並將結果存儲起來以備將來使用。這種簡單的優化將時間複雜度從指數級降低到多項式級。

例子:矩陣鏈乘法,最長公共子序列,旅行商問題,斐波那契數列

斐波那契序列:

fib (n)函數

如果n<=1返回n

返回fib(n-1) + fib(n-2)

解釋:在上麵的斐波那契數列示例中,來自每個子問題的結果都被存儲起來,以便進一步使用。

Baidu
map