Re: [問題] 動態規劃的問題

[ledia (下班後才下棋)]

※ 引述《henry035 (Rex)》之銘言：
: 簡化過的題目：
: 求整數 1 ~ N 組成和為 S 的方式有幾種？ (1 ~ N 各只能取一次)
: EX： N = 4 , S = 5 總共有兩種組成方式， 1 + 4 、 2 + 3
: 我用遞迴的方式列舉雖然可解，但太慢(超時)，請想問怎麼用動態規劃的演算法解？
: 有找到動態規劃的式子，如下：
: A[i][j] = A[i-1][j] + A[i-1][j-i]       j-i>=0
: A[i][j] = A[i-1][j]                     j-i< 0
: A[i][j] 代表 1 ~ i 使和為 j 的方法數
: 但實在不是很懂，想請問這是怎麼想出來的，而且為什麼是這樣？

  先假設 S >= N

  S 用 1 ~ N 的所有組法可分成兩種 case:

  (a) 有用到 N 的
  (b) 沒有用到 N 的

  (a) 用到 N 的那部份
      等於是 S-N 用 1 ~ (N-1) 組出來的每個解
      再附加 N 到最後面
      所以算次數就等價於去求用 1 ~ (N-1) 去組出 S-N

  (b) 沒有用到 N 的那部份的次數
      其實就等於是 S 用 1 ~ (N-1) 組出來的每個解

  容易證明 (a) 和 (b) 是不會互相重覆的, 而且包含全部可能
  (上一句是廢話, 一個有 N, 一個沒有 N 嘛 XD)

  由集合的加法原則
  我們可以推論出

  A[i][j] = A[i-1][j] + A[i-1][j-i]


  當然在 S < N 的時候

  (a) 是不存在的, 所以只有 (b) 的 case, 式子變成

  A[i][j] = A[i-1][j]


  這樣的說明有比較清楚嗎 ? ^^|

--

  有時候，遺忘，是令人快樂的。什麼時候？當然是有人傷了你的心的時候。
　存心傷你的那個人，固然是故意和你過不去，但是被傷了心而耿耿於懷的你
　，卻是和自己過不去了。所以，記性不好的人，通常會是比較快樂的人，也
　是比較不容易被擊倒的人。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.49
※ 編輯: ledia           來自: 140.112.30.49        (08/08 01:27)
推 henry035:概念了解了，也比較能體會怎麼從 Divide and Conquer
→ henry035:推演出這個想法，謝謝大大您費時解說。
→ henry035:但想追問一個問題，底層的數值要怎麼設呢？
→ henry035:A[2][3] = A[1][3] + [1][2] 但是
→ henry035:A[2][3] = 1, [1][3] = 0, A[1][2] = 0
→ ledia:A[2][3] = A[1][3] + A[1][1] ...... 我忘了提到了
→ ledia:初始值的話 1+...+i == j -> 1, 1+...+i < j -> 0
→ ledia:如果覺得某等式有問題, 就去直接拆解思考等號兩邊的真實意義
→ ledia:有例外就會找到例外, 式子代錯也可以因此發現
推 henry035:謝謝大大您指出我的腦殘錯誤~ 感謝
→ ledia:這不腦殘呀... 我一開始看到也在想是不是有什麼沒想到 XD