Re: [問題] 動態規劃的問題
※ 引述《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)
推
08/08 04:16, , 1F
08/08 04:16, 1F
→
08/08 04:16, , 2F
08/08 04:16, 2F
→
08/08 04:17, , 3F
08/08 04:17, 3F
→
08/08 04:18, , 4F
08/08 04:18, 4F
→
08/08 04:18, , 5F
08/08 04:18, 5F
→
08/08 10:59, , 6F
08/08 10:59, 6F
→
08/08 11:01, , 7F
08/08 11:01, 7F
→
08/08 11:02, , 8F
08/08 11:02, 8F
→
08/08 11:02, , 9F
08/08 11:02, 9F
推
08/08 11:28, , 10F
08/08 11:28, 10F
→
08/08 12:28, , 11F
08/08 12:28, 11F
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
