動(dòng)態(tài)規(guī)劃?Dynamic Programming

視頻1：動(dòng)態(tài)規(guī)劃入門：從記憶化搜索到遞推【基礎(chǔ)算法精講 17】

視頻2：0-1背包 完全背包【基礎(chǔ)算法精講 18】

視頻3：最長公共子序列 編輯距離【基礎(chǔ)算法精講 19】

視頻4：最長遞增子序列【基礎(chǔ)算法精講 20】

視頻5：買賣股票的最佳時(shí)機(jī)：無限次/冷凍期/k次【基礎(chǔ)算法精講 21】

視頻6：區(qū)間 DP：最長回文子序列 最優(yōu)三角剖分【基礎(chǔ)算法精講 22】

從記憶化搜索到遞推

0-1背包：

????這是0-1背包問題的模版，是“拿或不拿”問題的直譯。

完全背包：

????和0-1背包很相像，區(qū)別是某一件物品可以重復(fù)選，這是這類題的模版。

????另外需要自己額外注意一下動(dòng)態(tài)規(guī)劃的時(shí)候是否需要倒序進(jìn)行，參見靈神視頻。而且一般題目分為至多裝capacity，恰好裝滿capacity和至少裝capacity三種不同的變形，也需要代碼進(jìn)行相應(yīng)的調(diào)整。

最長公共子序列&編輯距離

最長遞增子序列

????另外值得一提的是：數(shù)組 nums 的最長遞增子序列（LIS）等價(jià)于 nums 與排序去重后的 nums 的最長公共子序列（LCS）：（例如 nums = [1,3,3,2,4]，排序去重后 = [1,2,3,4]，LCS = [1,3,4] 或 [1,2,4]）

狀態(tài)機(jī) DP

????這里可以把 j-1 寫在 dfs(i-1, j-1, 1) + prices[i] 中，然后 dfs(i-1, j, 0) - prices[i]，或者反過來也一樣，因?yàn)橛小举I入】肯定有【賣出】：

區(qū)間 DP