2w+字絕殺!動態(tài)規(guī)劃.pdf來了
前言
大家好，我是bigsai，好久不見，甚是想念。
今天給大家分享我的動態(tài)規(guī)劃原創(chuàng)的pdf，2w多字，里面囊括28道最經(jīng)典的動態(tài)規(guī)劃問題，可謂是絕殺利器(自吹一波)！
一直有朋友說動態(tài)規(guī)劃很難，確實(shí)動態(tài)規(guī)劃非常靈活，但是對于找工作來說，我們需要掌握的動態(tài)規(guī)劃其實(shí)相比競賽范疇那些復(fù)雜的沒那么難，一些狀態(tài)轉(zhuǎn)移方程、數(shù)組定義方式有的還是很容易看出來的，有的不容易看出來思考看別人解答也是可以理解的。
剛好現(xiàn)在?？偷囊粋€專欄筆刷101有動態(tài)規(guī)劃系列的題，我把里面和自己加了一些動態(tài)規(guī)劃的題目都寫了，我的實(shí)現(xiàn)是基于?？偷墓P刷101基礎(chǔ)，但我給了?？秃土鄣膶?yīng)鏈接的。
?？凸P刷101鏈接：https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
這個題庫總結(jié)不錯，建議大家刷一下。
什么是動態(tài)規(guī)劃
動態(tài)規(guī)劃的范圍雖然確實(shí)是很廣很難，但是從整個動態(tài)規(guī)劃出現(xiàn)的頻率來看，這幾種基礎(chǔ)的動態(tài)規(guī)劃理解容易，學(xué)習(xí)起來壓力不大，并且出現(xiàn)頻率非常高。
這幾個常見的動態(tài)規(guī)劃有：連續(xù)子數(shù)組最大和，子數(shù)組的最大乘積，最長遞增子序列(LIS)，最長公共子序列(LCS)，最長公共子串，最長公共子串，不同子序列。
首先很多人問，何為動態(tài)規(guī)劃？動態(tài)規(guī)劃（Dynamic Programming，DP）是運(yùn)籌學(xué)的一個分支，是求解決策過程最優(yōu)化的過程。通俗一點(diǎn)動態(tài)規(guī)劃就是從下往上(從前向后)階梯型求解數(shù)值。
那么動態(tài)規(guī)劃和遞歸有什么區(qū)別和聯(lián)系？
總的來說動態(tài)規(guī)劃從前向后，遞歸從后向前，兩者策略不同，并且一般動態(tài)規(guī)劃效率高于遞歸。
不過都要考慮初始狀態(tài)，上下層數(shù)據(jù)之間的聯(lián)系。很多時(shí)候用動態(tài)規(guī)劃能解決的問題，用遞歸也能解決不過很多時(shí)候效率不高可能會用到記憶化搜索。
對于一個動態(tài)規(guī)劃的問題來說，通常解決也是有技巧的，大致來說有以下幾個步驟：
確定dp數(shù)組含義：定義dp數(shù)組的維度以及dp數(shù)組定義(對應(yīng)下標(biāo)值的含義)。
確定遞推式：確定當(dāng)前下標(biāo)的dp值與前面已確定結(jié)果之間的關(guān)聯(lián)。
初始化dp數(shù)組：考慮dp數(shù)組的0號位置、邊緣位置以及特殊情況的一些值。
確定遍歷順序：正確的遍歷進(jìn)行dp推導(dǎo)，保證讓數(shù)據(jù)結(jié)果一層一層"鋪滿"。
當(dāng)然動態(tài)規(guī)劃也能有很多空間優(yōu)化，有些只用一次的值，你可以用一些變量去替代。有些二維數(shù)組很大也可以用一維數(shù)組交替替代。當(dāng)然動態(tài)規(guī)劃專題很大，有很多比如樹形dp、狀壓dp、背包問題等等經(jīng)常出現(xiàn)在競賽中，能力有限這里就將一些出現(xiàn)筆試高頻的動態(tài)規(guī)劃！
最后做動態(tài)規(guī)劃的問題時(shí)候，有幾個小建議一定要處理好：
多嘗試dp數(shù)組維度和含義，這個需要有一定的經(jīng)驗(yàn)才更好。
初始、邊緣等情況初始情況好好考慮，要讓初始、邊緣等能夠正常參與遞推。
推導(dǎo)狀態(tài)轉(zhuǎn)移時(shí)候要跳出思維限定，只尋找這個結(jié)果和前面的聯(lián)系(不要考慮前面哪里來的、前面值是否正確之類)，這點(diǎn)和有遞歸信賴是有點(diǎn)類似的。
不太明白?看完這些題解你應(yīng)該會明白：
部分截圖
結(jié)語
這個其實(shí)還沒有完全完善(在dp系列還沒有做好歸納總結(jié)，缺一些)，但是鑒于很多人需要，我就先分享給大家了，暫時(shí)先不放在公眾號分享給大家(后面完善再放到公眾號)，有些不錯的經(jīng)典題后面也會單獨(dú)作為文章發(fā)出來分享交流。
后續(xù)都會同步到倉庫中，還求個star：https://github.com/javasmall/bigsai-algorithm
獲取方式：
分享在交流群中，有我好友的可以直接問我要，可以分享給好友
加我好友(
bigsai66)備注(動態(tài)規(guī)劃)我發(fā)給你。
因?yàn)檎肀容^粗糙，難免可能有些差錯，先分享給一部分人看看，有問題修修改改然后不斷完善，最近有點(diǎn)忙無法保證輸出，咱們后面再見！
歡迎添加?「bigsai66」，備注[動態(tài)規(guī)劃]
好東西記得分享(點(diǎn)贊、再看)一下