4， 不記錄每一個(gè)子問(wèn)題的解（區(qū)別于動(dòng)態(tài)規(guī)劃2）

4， 并且存在化簡(jiǎn)狀態(tài)表達(dá)， 使其更加簡(jiǎn)潔的可能

動(dòng)態(tài)規(guī)劃其實(shí)是由暴力遞歸演變而來(lái)的，每個(gè)動(dòng)態(tài)規(guī)劃的接法基本都能找到其動(dòng)態(tài)規(guī)劃的版本~

他們的關(guān)系如下：

暴力遞歸------》依賴(lài)關(guān)系（套路，即記憶關(guān)系）------》動(dòng)態(tài)規(guī)劃

下面以一道題為例子來(lái)向大家詳細(xì)的介紹一下：

先理解一下題意：

給定一個(gè)數(shù)組和一個(gè)整數(shù)，可以隨便選擇arr數(shù)組里面的數(shù)字，看看累加起來(lái)能不能得到aim，可以得到就返回true，不可以返回false

eg ：arr[] = { 3, 2, 9, 7 }; ?Aim = 21;返回true 3+2+9+7=21

????????arr[] = { 3, 2, 9, 7 };?Aim = 13;返回false，無(wú)法組合得到13

思路分析：

先用暴力遞歸的方式來(lái)解決：

先看一下方法的參數(shù)，參數(shù)有arr[]和Aim是題目提供的，我們自己定義的有i和sum，這兩個(gè)參數(shù)是什么意思呢？

他們的含義是，在一個(gè)數(shù)組中，從i下標(biāo)開(kāi)始，可以任意去i后面的數(shù)進(jìn)行累加，累加的和為sum，看圖：

如果你能想到這個(gè)圖或者說(shuō)看到這個(gè)圖，你就已經(jīng)成功了一半~~

可以發(fā)現(xiàn)，要判斷這個(gè)數(shù)組中是否有滿足要求的組合，只要看最后一行是否有相應(yīng)的aim值就可以了。

所以，就有了下面的暴力遞歸：

暴力遞歸之后，就是動(dòng)態(tài)規(guī)劃了~

來(lái)來(lái)來(lái)，重點(diǎn)來(lái)了，從暴力遞歸轉(zhuǎn)變到動(dòng)態(tài)規(guī)劃，跟題意是沒(méi)有半毛錢(qián)關(guān)系的~

下面劃重點(diǎn)了：

暴力遞歸------》依賴(lài)關(guān)系（套路，即記憶關(guān)系）------》動(dòng)態(tài)規(guī)劃

這里還差了個(gè)依賴(lài)關(guān)系：

啥都別說(shuō)了，先畫(huà)個(gè)圖吧嘻嘻~

還是以上面那個(gè)例子為主：

arr[3] = {2,3,7};

aim = 10;

那么i的取值范圍就是0~3了

sum的取值則是2+3+7=12即（0~12）

先看暴力破解法的basecase：

辣么，第三行sum等于Aim的值就為true，其他為false；

再看基本關(guān)系：

通過(guò)細(xì)細(xì)分析，可以得到下面的依賴(lài)關(guān)系圖了~

圖中的方框加×是（i，sum）的依賴(lài)，也就是說(shuō)，要想得到（I，sum）的值，只要知道兩個(gè)方框加×里面的值就可以推出來(lái)了（ 不是我說(shuō)的，是程序里面體現(xiàn)出來(lái)的）那么，因?yàn)榈谌械闹刀贾懒?#xff0c;那么其他列的值肯定也可以通過(guò)這一列的值推出來(lái)，那么我們所要求的（0，0）的值不就出來(lái)了嗎？

這個(gè)依賴(lài)關(guān)系出來(lái)之后，那么動(dòng)態(tài)規(guī)劃的解也就出來(lái)了~~~（開(kāi)心）

其實(shí)這個(gè)方法我也是思考了很久才領(lǐng)悟的~

希望對(duì)你們也能有所幫助~~不懂歡迎留言，懂得幫忙點(diǎn)個(gè)贊~~~

總結(jié)

以上是生活随笔為你收集整理的史上最容易理解的暴力递归和动态规划~~的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。