韩国理伦电影三级办公室,色婷婷亚洲一区二区三区肤色狂欢,久久欧美AⅤ无码精品久久,人妻少妇偷人无码视频

1. 動(dòng)態(tài)規(guī)劃解決了什么

我們知道的思想就是將大問題拆分成小問題進(jìn)行攻破;
比如鋼條切割問題：

給定一段長度為n的鋼條和如下的價(jià)格表，求切割鋼條方案，使得收益最大

我們很容易想到通過遞歸進(jìn)行求解：
假設(shè)price(x)代表長度x的鋼材的最大收益,我們很容易將問題進(jìn)行遞歸分解：
price(n) = max(pi, price(1)+price(n-1), price(2)+price(n-2),....,price(n-1)+price(1) );   

比如，我們求解一根長度為4的鋼材的切割方式：
就是求取各種組合的最大利益
price(4) = max(p4, price(1) + price(3), price(2) + price(2), price(3) + price(1));

那么接下來就是求解，price(3)、price(2)、price(1)的問題了；
這種自頂向下分解遞歸的方式肯定是可以解決這個(gè)鋼條切割的問題的，但是有沒有缺陷？
有的，還不小，就是效率問題。
隨著x的增大，遞歸的效率會(huì)越來越低，運(yùn)行速度會(huì)很慢，因?yàn)槭裁矗?br /> 因?yàn)樗诜磸?fù)求解相同的問題
在price(3)時(shí)，其已經(jīng)計(jì)算過3的最優(yōu)解了，且2、1的肯定也有了；
作為人類，我們自然而然就會(huì)將這個(gè)結(jié)果記住，并用于下次計(jì)算；
但是遞歸不會(huì)，在price(4)的時(shí)候，其仍然還會(huì)計(jì)算price(3),price(2),price(1），不管是不是上次遞歸已經(jīng)計(jì)算過了。
復(fù)制代碼
那么解決這個(gè)問題的很簡單的辦法是什么？
沒錯(cuò)，就是
將先前解決的子問題，進(jìn)行存儲(chǔ)，以減少重復(fù)計(jì)算！
這就是
好了，貌似我們討論到現(xiàn)在都是說的遞歸問題，其實(shí)呢，到目前為止，我們已經(jīng)講完了動(dòng)態(tài)規(guī)劃的本質(zhì)：

2. 什么是動(dòng)態(tài)規(guī)劃

1.動(dòng)態(tài)規(guī)劃是通過組合子問題的解來解決原問題
2.動(dòng)態(tài)規(guī)劃應(yīng)用于子問題重疊的情況，即不同的子問題具有公共的子子問題
3.動(dòng)態(tài)規(guī)劃算法對每個(gè)子子問題只求解一次
4.動(dòng)態(tài)規(guī)劃通常用來求解最優(yōu)化問題
復(fù)制代碼
動(dòng)態(tài)規(guī)劃算法：
1.刻畫一個(gè)最優(yōu)解的結(jié)構(gòu)特征
2.遞歸的定義最優(yōu)解的值
3.計(jì)算最優(yōu)解的值，通常自底向上
4.利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解
復(fù)制代碼
好了，讓我們用動(dòng)態(tài)規(guī)劃解一下鋼條切割問題：
1.刻畫一個(gè)最優(yōu)解的結(jié)構(gòu)特征
遞歸法中已經(jīng)刻畫的很清楚了
2.遞歸的定義最優(yōu)解的值
公式也在上面寫過了
3.計(jì)算最優(yōu)解的值，通常自底向上
通過帶備忘的自頂向下遞歸法，我們成功的比較高效的解決了鋼鐵切割的問題，這也是動(dòng)態(tài)規(guī)劃的一種方式,有沒有其他方式？
有的，對應(yīng)于自頂而下，我們采用自底而上的方式，將子問題按照從小到大的順序進(jìn)行求解，當(dāng)然還是得有備忘機(jī)制。
大部分情況下，自頂而下和自底而上的效率是近似的；但是呢，在某些特殊情況，自頂向下方法并未真正的遞歸考察所有可能的子問題；而且自底向上也沒有頻繁的遞歸函數(shù)的開銷；
所以，一般動(dòng)態(tài)規(guī)劃都是采用自底向上的方法，將復(fù)雜的問題，變成了簡單的多項(xiàng)式相加。
4.利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解
這條就更簡單了，既然你算法都寫出來了，在算法的途中，加上最優(yōu)解的存儲(chǔ)及輸出就可以了，
比如動(dòng)態(tài)規(guī)劃鋼鐵切割問題，在算法最初，我們關(guān)心的是price(n)，計(jì)算出最佳的收益；
最后我們只要在編寫出的算法中，加上輸出鋼鐵的分割就可以了。
復(fù)制代碼

3. 典型的動(dòng)態(tài)規(guī)劃

鋼鐵切割問題本身就是個(gè)典型的動(dòng)態(tài)規(guī)劃，除了這個(gè)例子，還有：
最長公共子序列
最優(yōu)二叉搜索樹
矩陣鏈乘法
....
復(fù)制代碼
不管是什么問題，本質(zhì)上我們都是通過層層分解子問題，并進(jìn)行組合；
如果這個(gè)問題，滿足上述特性，那么動(dòng)態(tài)規(guī)劃就是這些問題可能的解決方法之一。
某些問題是否適用于動(dòng)態(tài)規(guī)劃算法，你可以從如下角度：
1.是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)
    如果一個(gè)問題的最優(yōu)解，包含其子問題的最優(yōu)解
2.具有重疊子問題性質(zhì)
    問題的遞歸算法會(huì)反復(fù)求解相同的子問題
復(fù)制代碼
算法的精髓在于，其沒有最好，只有最合適

<pre id="wsmcu"></pre>