之前也在看算法相關(guān)的書、在被稱為黑書的《算法導(dǎo)論》里看過(guò)關(guān)于動(dòng)態(tài)規(guī)劃的講解

只是當(dāng)時(shí)研究不深、最近突來(lái)興趣對(duì)動(dòng)態(tài)規(guī)劃做了個(gè)小的總結(jié)、所以就分享下

不足之處多多指正、

先對(duì)動(dòng)態(tài)規(guī)劃做一個(gè)簡(jiǎn)單的介紹吧：

動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程(decision process)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)

學(xué)家R.E.Bellman等人提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，利用各階段之間的關(guān)系，逐個(gè)求解，

創(chuàng)立了解決這類過(guò)程優(yōu)化問(wèn)題的新方法——?jiǎng)討B(tài)規(guī)劃。
動(dòng)態(tài)規(guī)劃是信息學(xué)競(jìng)賽中選手必須熟練掌握的一種算法,他以其多元性廣受出題者的喜愛.  動(dòng)態(tài)規(guī)劃成為信息學(xué)奧賽的必考算法之一。
動(dòng)態(tài)規(guī)劃問(wèn)世以來(lái)，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫(kù)存管理、資源分配、設(shè)備更新、排序、裝載等問(wèn)題。

Main idea:
solve several smaller (overlapping) subproblems
record solutions in a table so that each subproblem is only solved once
final state of the table will be (or contain) solution

對(duì)于動(dòng)態(tài)規(guī)劃，我是這樣理解的：
把待解決的問(wèn)題分為一個(gè)規(guī)模較原問(wèn)題小的子問(wèn)題、

然后要考慮的就是如何更具這個(gè)子問(wèn)題如何得到原問(wèn)題的解已經(jīng)如何解決這個(gè)子問(wèn)題

當(dāng)然、原問(wèn)題和子問(wèn)題需要有相同的解決方式、它們只有問(wèn)題規(guī)模的區(qū)別。

這樣講有點(diǎn)抽象、用一個(gè)簡(jiǎn)單的圖來(lái)說(shuō)明下：

可以簡(jiǎn)單的這樣理解、把原問(wèn)題劃分為小的問(wèn)題（能組合成原問(wèn)題的，小的問(wèn)題再劃分、持續(xù)下去，找到簡(jiǎn)單解

反方向計(jì)算回來(lái)（記下每一步結(jié)果）最后就能得到解。

聽起來(lái)似乎不難，但是要作比較深入的理解還是得通過(guò)實(shí)例說(shuō)話

后面會(huì)跟幾個(gè)經(jīng)典例子、諸如背包問(wèn)題等等的都會(huì)有我自己的理解、

如果都能理解的話、恭喜你，動(dòng)態(tài)規(guī)劃入門了