動態(tài)規(guī)劃到底是不是一種算法呢？
時間：2023-10-19 05:42:01 | 來源：網(wǎng)站運(yùn)營
時間：2023-10-19 05:42:01 來源：網(wǎng)站運(yùn)營
動態(tài)規(guī)劃到底是不是一種算法呢？：動態(tài)規(guī)劃并不是一種算法，而是一種思想。
類似的，還有貪心。
我認(rèn)為你看到的當(dāng)成一種算法，應(yīng)該說是當(dāng)做一個考點(diǎn)。畢竟對于競賽/考試來說，有明確的考綱還是比較重要的。
貪心并不是一種算法，只是一種用滿足局部最優(yōu)來達(dá)到全局最優(yōu)(需要嚴(yán)格的證明)的思想。
動態(tài)規(guī)劃是一種在搜索中通過合并相同的狀態(tài)來減少不必要的時間/空間開支的思想。
舉個例子，動態(tài)規(guī)劃最經(jīng)典的01背包問題，最原始的是回溯法暴力搜索，復(fù)雜度為O(2^n)，而我們可以注意到在搜索過程中，我們并不在意總價值為x的時候，到底用了哪些物品。甚至也不在意是用了1個物品還是2個物品。這時候我們就可以把總價值為x的所有狀態(tài)合并成1個狀態(tài)。從搜索樹上來看，就是把若干個子樹合并成一個節(jié)點(diǎn)。注意到這樣的合并是非常有意義的，因?yàn)樯疃葹閘的子樹的節(jié)點(diǎn)個數(shù)是2^l個。
另一個經(jīng)典的例子是最長公共子序列，暴力搜索的復(fù)雜度是O(2^n*2^m)，但是我們其實(shí)并不在乎在第一個串的前i個字符和第二個串的前j個字符的最長公共子序列長度為k，是哪k個字符。因此這時候我們把只要能構(gòu)成第一個串的前i個字符和第二個串的前j個字符的最長公共子序列長度為k的情況都合并了。
關(guān)鍵詞：規(guī)劃,動態(tài)
在線咨詢