<sub id="gqw76"><listing id="gqw76"></listing></sub>
      <sub id="gqw76"><listing id="gqw76"></listing></sub>

    1. <form id="gqw76"><legend id="gqw76"></legend></form>
    2. 圖解 | 原來這就是動態規劃

      1

      小宇:閃客,我最近在研究動態規劃,但感覺就是想不明白,你能不能給我講講呀?

      閃客:沒問題,這個我擅長,你先說說提到動態規劃,你最先想到的是什么?

      小宇:就什么子問題呀、狀態轉移方程呀亂七八糟的,哎呀不行不行,我一想到這些腦子又嗡嗡響了。

      閃客:你先別急,你先把所有的名詞都拋在腦后,聽我講。

      小宇:好滴,你說吧。

      閃客:小宇我問你,從 1 一直加到 100 等于多少?

      1 + 2 + 3 + ... + 100 = ?

      小宇:5050!

      閃客:你這,怎么不按套路出牌呀,你應該說不知道。

      小宇:人家高斯早就算出來了,我還裝不知道,這也太假了吧。

      全劇終...

      2

      閃客:好吧,那我再給你出一個題。

      小宇:行,你說吧,這回我肯定說不知道。

      閃客:一個樓梯有 10 級臺階,你從下往上走,每跨一步只能向上邁 1 級或者 2 級臺階,請問一共有多少種走法?

      小宇:額,這我真不知道了,我想想哈。

       

      小宇:不行了不行了,實在想不明白,想了后面的就忘了前面的。

      閃客:你還是陷入了窮舉的思想,你仔細想想我給你出的第一個題,看看有沒有思路。

      小宇:啊!原來是有關聯的呀。

      閃客:對呀,我本來想說假如我告訴你 1+...+99 是多少,你是不是就直接能算出 1+...+100 的值了。

      小宇:哦你這么一提示我有點感覺了!要想走到第 10 級臺階,要么是先走到第 9 級,然后再邁一步 1 級臺階上去,要么是先走到第 8 級,然后一次邁 2 級臺階上去。

       

      閃客:太棒了!你找到感覺了!接著往下說。

      小宇:這樣的話,走到 10 級臺階的走法數,就等于走到 9 級臺階的走法數,加上走到 8 級臺階的走法數。

      閃客:很好,那假如走到第 x 級臺階的走法數我們定義為 F(x),那你能把剛剛的描述公式化么?

      小宇:那太簡單了,公式就是:

      F(10) = F(9) + F(8)

      閃客:沒錯,而且不光是 10 級臺階如此,走到任何一級臺階的走法數,都符合這個邏輯,因此就可以得出一個通用公式:

      F(x) = F(x-1) + F(x-2)

      小宇:嗯嗯,這樣計算 F(10),只需要知道 F(9) 和 F(8) 就可以了,而計算 F(8),就只需要知道 F(7) 和 F(6) 就可以了,依次類推。

      閃客:沒錯,那你想想看 F(2) 和 F(1) 怎么計算?

      小宇:簡單,還是剛剛都邏輯被,想知道 F(2),只需要知道 F(1) 和 F(0),誒不對 F(0) 是什么鬼?還有 F(1) 的計算需要知道 F(0) 和 F(-1),不行呀,這解釋不通了。

      閃客:哈哈,別急,在這道題里,如果只邁到 1 級臺階,那一共就一種走法;如果只邁到 2 級臺階,就只有兩種走法。可以直接很直觀地得出,沒必要推導。

       

      小宇:哦哦我懂了,這道題里由于每一個遞推項都需要前兩項的支持,所以必須有最開頭的兩項作為已知,就是你說的 F(1) = 1 和 F(2) = 2。

      閃客:沒錯。

      小宇:嗯嗯,感覺這樣就推出全部結果了!我寫一下程序你看看。

      閃客:先別急,由于這道題是一道經典的動態規劃題,所以我們以這道題為例子來定義動態規劃的三要素,在本題中

      F(x-1) 和 F(x-2) 被稱為 F(x) 的最優子結構

      F(x) = F(x-1) + F(x-2) 叫狀態轉移方程

      F(1) = 1, F(2) = 2 是問題的邊界

      之后做動態規劃問題,只要找好這三個要素就好了。

      小宇:哇,升華了誒,逼格瞬間高了不少呢。

      閃客:先別說這些廢話了,那接下來你看看能不能寫出程序,計算出 F(10) 的結果,這才是難點。

      小宇:編程的話這似乎是個遞歸問題,簡單!

      int getWays(int n) {
          if (n == 1) {
              return 1;
          }
          if (n == 2) {
              return 2;
          }
          return getWays(n-1) + getWays(n-2);
      }

       

      閃客:嗯不錯,這樣很簡潔,但復雜度太高了,是 O(2^n),具體你可以之后想想為什么。現在你看看能不能將復雜度降低。

      小宇:我想想看,計算 F(10) 時需要計算 F(9) 和 F(8),而在遞歸計算 F(9) 時要計算 F(8) 和 F(7),這樣 F(8) 在這里重復計算了,浪費了時間。

       

      閃客:沒錯,其實計算新一個階段的值,只需要一直將其前兩個階段的值保存起來,就可以一直算到最終的結果了。比如定義兩個變量 a 和 b 用于存儲前兩個階段的值,在計算 F(3) 時。

       

      臺階

      1

      2

      3

      4

      ...

      10

      走法

      a=1

      b=2

      3

       

       

       

       
       
       

      計算 F(4) 時,F(1) 的值就不用保存了,a 和 b 依次替換新值。

       

      臺階

      1

      2

      3

      4

      ...

      10

      走法

       

      a=2

      b=3

      5

       

       

       
       
       

      依此類推,最終就算出了 F(10) 的值。

       

      臺階

      1

      2

      ...

      8

      9

      10

      走法

       

       

       

      a=34

      b=55

      89

       
       
       

      當然你也可以把之前的值都保留,但這樣就增加了空間復雜度,看你的需求了。

      小宇:好的,那這樣代碼也很好寫,就這樣。

      int getWays2(int n) {
          if (n == 1) {
              return 1;
          }
          if (n == 2) {
              return 2;
          }
          int a = 1;
          int b = 2;
          int temp = 0;
          for (int i = 3; i <= n; i++) {
              temp = a + b;
              a = b;
              b = temp;
          }
          return temp;
      }

       

      閃客:不錯,這就是這道題正確的動態規劃解法,而且時間復雜度是 O(N),空間復雜度是 O(1)

      小宇:哇,這就是動態規劃呀,原來這么簡單。

      3

      閃客:不錯,動態規劃理解起來不難,難在當需要考慮的因素,也就是變化的維度多起來的時候,有的人就會頭腦發蒙,不好找遞推公式了,而且這也確實是個難點。

      小宇:哦是嗎?

      閃客:那當然,我再給你出一道題。

      小宇:來吧兄弟。

      閃客:咳咳,那你聽好了。

      有一個背包,可以裝載重量為 5kg 的物品。

      有 4 個物品,他們的重量和價值如下。

       

      那么請問,在不得超過背包的承重的情況下,將哪些物品放入背包,可以使得總價值最大?

      小宇:明白了,就是我用這個背包最多能裝走多少錢的東西。

      閃客:是的。

      小宇:哎呀不行,我又陷入走樓梯時的遍歷思想了。

      閃客:沒關系,這道題能想出遍歷思想,其實也不容易了,你可以先說一下,找找感覺。

      小宇:嗯嗯,那就是每個物品都可以有放入背包不放入背包兩種選擇。

      如果總重量超過了背包承重,那就不算,或者說將價值記為 0,然后將所有情況中價值最大的那個作為結果。

      這樣的復雜度也很容易得出,就是 O(2^N)

      閃客:沒錯,這個復雜度很高的算法你已經說的很明白了,那接下來你想想看用動態規劃思想,能不能解決這個問題。

      小宇:好的,你之前說過,動態規劃的三要素是最優子結構、狀態轉移方程和邊界

      閃客:沒錯,之前的變量很少所以比較簡單,現在變量多了,定義就變得難了起來,我們先來幾個定義方便描述。我們將 4 個物品的重量和價值分別表示為:w1,w2,w3,w4,v1,v2,v3,v4。

       

      假如我們用

      F(W,i)

      表示

      用載重為 W 的背包,裝前 i 件物品的最大價值

      那本題其實就是

      用載重為 5kg 的背包,裝前 4 件物品的最大價值

      其實就是求解

      F(5,4)

      你能找到狀態轉移方程么?

      小宇:我想想,單看這個物品 4,有兩種可能:

      第一種可能:如果選擇把它裝入背包,那已經得到了 6 元錢。

      此時背包剩余載重為 1kg(5kg-4kg),剩余物品是除去物品 4 后的前 3 件物品。

      那這部分能獲取到的最大價值,相當于

      用一個載重為 1kg 的背包,裝前 3 件物品的最大價值

      哇,那這部分就是

      F(1,3)

      閃客:哈哈,你這自己說著說著就說對啦!

      小宇:所以最終,如果選擇將物品 4 放入背包,這種情況下,最大價值就等于二者之和。

      F(1, 3) + 6

       

      閃客:太好了小宇,那另一種情況呢?

      小宇:第二種可能:如果選擇不裝這個物品 4,那更簡單了,就直接等于用一個載重為 5 的背包裝前 3 件物品的價值。

      F(5, 3)

       

      閃客:沒錯,而且就只有這兩種情況!所以你看看 F(5,4)是否能用這兩種情況的值表示呢?

      小宇:哈哈,很簡單,就等于這兩種情況當中的最大值唄。

      F(5,4) = max { F(1, 3) + 6,F(5, 3) }

      閃客:太好了,現在狀態轉移方程出來了,此時我們畫個表格。

       

      我們的目標就是要計算右下角那個值,即背包載重 W = 5 時,選擇前 4 件物品放入背包的最大價值 F(5,4)

      小宇:哇這個表格好清晰呀,根據上面的公式

      F(5,4) = max { F(1,3) + 6, F(5,3) }

      那也就是說只要知道 F(1,3) 和 F(5,3) 的值就可以了對吧?

       

      閃客:沒錯,那你再看看 F(1,3) 怎么計算?

      小宇:好的,F(1,3) 此時背包重量為 1,如果選擇放第三件物品的話,誒?好像不行,第三件物品根本放不下呀!

      閃客:是的,所以這種情況就沒必要討論放第三件物品的情況了,因為根本放不下,因此 F(1,3) 直接就等于 F(1,2),所以只需要知道 F(1,2) 即可。

       

      同理 F(1,2) 也直接等于 F(1,1),因為在背包重量為 1 時第二件物品也放不下。

       

      閃客:小宇你想想看,那 F(1,1) 又等于什么呢?

      小宇:顯然嘛,現在只有一件物品可以選了,那能放下當然就放咯,所以最大價值就是第一件物品的價值 3,即 F(1,1) = 3

      閃客:沒錯,這樣我們就找到了一個邊界值,小宇你想想看還有哪些邊界值可以直接得出?你寫在表格里吧。

      小宇:好的,首先第一列表示背包重量為 0 時的情況,那顯然什么都裝不了,就全都是 0 了。

       

      然后第一行也比較好算,背包重量 >= 1 時可以放下第一件物品,所以最大價值都等于 3

       

      閃客:很好,接下來,就依次把表格的所有項都填出來,自然就可以算出 F(5,4) 啦。

       

      小宇:哇塞,這樣看好清晰呀!

      閃客:是呀,不過剛剛我們用的都是具體的數字,那我們試著把這個問題抽象化,用一個載重為 W 的背包,裝載 N 件物品,每件物品的重量和價值分別用 wi 和 vi 來表示,那剛剛的狀態轉移方程是什么呢?

      小宇:emm,剛剛 F(5,4) = max { F(1,3) + 6, F(5,3) },如果都用變量表示的話,就是

      F(W,N) = max { F(W-wn, N-1) + vn,F(W, N-1) }

      閃客:很好,這就是狀態轉移方程

      F(W-wn, N-1) 和 F(W, N-1) 就是 F(W,N) 的最優子結構

      而剛剛表格中的第一行和第一列,即 F(0,...) 和 F(...,1) 就是邊界值

      小宇:哇塞我愛你閃客!終于有點理解動態規劃的思想了呢!

      4

      閃客:別高興太早,雖然過程看著清晰了,但代碼寫起來還是有難度的,你今天回去就把代碼試著實現一下吧。

      小宇:好的,保證完成任務。

      閃客:快到晚飯時間了,旁邊新開了家餃子館,要不要一塊去吃呀?

      小宇:哦不了,晚上想利用晚飯時間再去消化消化動態規劃的知識,不是還得代碼實現呢么,下次吧,

      閃客:哦好吧~

       

      后記

       

      本文通過直觀演示 01 背包問題的解題思路,簡單說明了動態規劃思想的算法核心。可能不少人覺得動態規劃難在理解,所以花很多時間在理解其思想上。但其實理解核心思想,這一篇文章就夠了,更多的是通過不斷做題,反過來幫助自己理解動態規劃的思想。所以希望讀者在讀完本文后,和小宇一樣,動手將其代碼實現,并找來其他變種題目,繼續鞏固。

      posted @ 2021-02-25 19:51  閃客sun  閱讀(2975)  評論(12編輯  收藏
      最新chease0ldman老人|无码亚洲人妻下载|大香蕉在线看好吊妞视频这里有精品www|亚洲色情综合网

        <sub id="gqw76"><listing id="gqw76"></listing></sub>
        <sub id="gqw76"><listing id="gqw76"></listing></sub>

      1. <form id="gqw76"><legend id="gqw76"></legend></form>