[問題] 動態規劃的問題

[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 的方法數

但實在不是很懂，想請問這是怎麼想出來的，而且為什麼是這樣？


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.133.18.7
推 LPH66:把 A[i][j] 的意思代進式子裡你就了解了
→ henry035:有代過，但還是不太懂為什麼這樣就能得解，而且怎建構出
→ henry035:式子的想法 ... @@
推 su31o4gj83:以你舉的例子來看, A[3][5]代表不包含4有幾種組法
→ su31o4gj83:A[3][1]代表必定包含4有幾種組法
推 FTM:A[2][3] = 1, but A[1][3] = 0, A[1][2] = 0 ?
→ henry035:我了解s大的意思，但還是頗困惑，而且也有同樓上的問題
→ henry035:想這問題想到質疑起自己的智商是不是有問題...囧rz|||
→ netsphere:同樣問題 動態規劃的式子可以有好幾種喔~
→ henry035:那這題還有哪些可行的想法或式子呢？