动态规划学习笔记
2019獨(dú)角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>
感謝知識(shí)來(lái)源：
演算法筆記：http://www.csie.ntnu.edu.tw/~u91029/
動(dòng)態(tài)規(guī)劃：從新手到專(zhuān)家：http://hawstein.com/posts/dp-novice-to-advanced.html
以及 老師、助教、學(xué)長(zhǎng)、同學(xué)
-------------------------------------------分割線-------------------------------------------------------------------
????分而治之的觀點(diǎn)
將大問(wèn)題分解成為若干個(gè)子問(wèn)題，使得問(wèn)題的復(fù)雜程度下降，但是如何做一個(gè)【好的】分解呢？
例子：分解動(dòng)作，將帶球上籃分解會(huì)三個(gè)動(dòng)作，如果這些動(dòng)作仍然很難那么繼續(xù)分解直至簡(jiǎn)單。
積分求面積
動(dòng)態(tài)規(guī)劃是分治法運(yùn)用記憶延伸
動(dòng)態(tài)規(guī)劃是執(zhí)行如下的“變換”：
問(wèn)題-->狀態(tài)
全部問(wèn)題-->狀態(tài)空間
遞歸公式-->狀態(tài)轉(zhuǎn)移方程
動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)步驟
分而治之
子問(wèn)題與原問(wèn)題有同樣的計(jì)算方式
該問(wèn)題反復(fù)出現(xiàn)
設(shè)計(jì)計(jì)算過(guò)程
哪些問(wèn)題需要計(jì)算
需要計(jì)算多少個(gè)
定義表格來(lái)儲(chǔ)存
決定計(jì)算順序
設(shè)定初始值，劃定范圍
實(shí)現(xiàn)
上到下
下到上
交大OJ上的動(dòng)態(tài)規(guī)劃題目：
1002 ?二維DP
1013? 完全背包
3029
2204
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1088
1089
1090
1091
1092
轉(zhuǎn)載于:https://my.oschina.net/xueyang/blog/387270
總結(jié)
