PTT數位生活區 / C_and_CPP (C/C++)

[問題] 動態規劃的問題

看板C_and_CPP (C/C++)作者 (Rex)時間16年前 (2009/08/07 22:02), 編輯推噓3(3推 0噓 7→)
留言10則, 5人參與, 最新討論串1/2 (看更多)
簡化過的題目： 求整數 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 的方法數 但實在不是很懂，想請問這是怎麼想出來的，而且為什麼是這樣？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.133.18.7
推
08/07 22:06, , 1F
把 A[i][j] 的意思代進式子裡你就了解了
08/07 22:06, 1F
→
08/07 22:28, , 2F
有代過，但還是不太懂為什麼這樣就能得解，而且怎建構出
08/07 22:28, 2F
→
08/07 22:28, , 3F
式子的想法 ... @@
08/07 22:28, 3F
推
08/07 23:14, , 4F
以你舉的例子來看, A[3][5]代表不包含4有幾種組法
08/07 23:14, 4F
→
08/07 23:15, , 5F
A[3][1]代表必定包含4有幾種組法
08/07 23:15, 5F
推
08/07 23:44, , 6F
A[2][3] = 1, but A[1][3] = 0, A[1][2] = 0 ?
08/07 23:44, 6F
→
08/08 00:10, , 7F
我了解s大的意思，但還是頗困惑，而且也有同樓上的問題
08/08 00:10, 7F
→
08/08 00:30, , 8F
想這問題想到質疑起自己的智商是不是有問題...囧rz|||
08/08 00:30, 8F
→
08/08 09:22, , 9F
同樣問題 動態規劃的式子可以有好幾種喔~
08/08 09:22, 9F
→
08/08 10:38, , 10F
那這題還有哪些可行的想法或式子呢？
08/08 10:38, 10F
‣ 更多 henry035 的文章
文章代碼(AID): #1AV3FUE1 (C_and_CPP)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共2篇)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 henry035 的文章
文章代碼(AID): #1AV3FUE1 (C_and_CPP)