算法競賽進階指南：自然數拆分（Python）

題目描述：

給定一個自然數 N，要求把 N 拆分成若干個正整數相加的形式，參與加法運算的數可以重復。

注意:

• 拆分方案不考慮順序；
• 至少拆分成 2 個數的和。

求拆分的方案數 mod2147483648 的結果。

輸入格式

一個自然數 N。

輸出格式

輸入一個整數，表示結果。

數據范圍

1≤N≤4000

輸入樣例：

7

輸出樣例：

14

題目分析： 

很明顯是完全背包的模型 將最後要得到的數看作背包的體積 將湊出該數的每一個數看作物品的體積

因此問題轉化成了 完全背包求填滿背包的方案數

我們考慮先用樸素版的dp

dp[i][j] 表示用前i個物品恰好填滿體積為j的背包 狀態轉移方程如下：

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

那麼這個式子怎麼來的呢？首先這是一個完全背包 所以同一個物品可以重復選擇 所以可列出如下等式：dp[i][j] = dp[i-1][j] + dp[i-1][j-vi] + dp[i-1][j-2vi] + .... + dp[i-1][j-nvi]

其中 n*vi 小於 j

接下來簡化這個式子 通過另一個等式：

dp[i][j-vi] = dp[i-1][j-vi] + dp[i-1][j-2vi] + ... + dp[i-1][j-nvi]

為什麼這兩個等式能列出來 請淺思考一下等式表達的含義即能理解

我們觀察如下標紅的兩部分：

dp[i][j] = dp[i-1][j] + dp[i-1][j-vi] + dp[i-1][j-2vi] + .... + dp[i-1][j-nvi]

dp[i][j-vi] = dp[i-1][j-vi] + dp[i-1][j-2vi] + ... + dp[i-1][j-nvi]

可以發現他們是相等的 所以原式可以簡化為 ：dp[i][j] = dp[i-1][j] + dp[i][j-vi]

即為狀態轉移方程

完整代碼如下 ： 

N = int(input())
dp = [[0 for i in range(N+1)]for j in range(N+1)]
dp[0][0] = 1
for i in range(1,N) :
for j in range(N+1) :
dp[i][j] = dp[i-1][j]
if j >= i : dp[i][j] += dp[i][j-i]
print(dp[N-1][N]%2147483648)

很遺憾 測試數據卡了空間 該代碼只能過 8/10 個測試點 所以我們考慮優化掉一維空間 

我們可以發現 無論是 dp[i-1][j] 還是 dp[i][j-vi] 相對於dp[i][j] 而言都是會被先計算的狀態

而且 dp[i][j]也只與這兩個狀態相關 進一步觀察可以發現 對於dp[i][j]而言 它用到的狀態一定是本層i 的 j-vi 和上一層i-1 的 j  因此我們其實並不需要保存i這一維變量

因為dp[j-vi] 和 dp[j] 一定等於 p[i][j-vi] 和 dp[i-1][j] （這裡請仔細思考清楚）

所以狀態轉移方程可以簡化成 ：dp[j] = dp[j] + dp[j-vi]

AC代碼 

N = int(input())
dp = [0 for i in range(N+1)]
dp[0] = 1
for i in range(1,N) :
for j in range(i,N+1) :
dp[j] += dp[j-i]
print(dp[N]%2147483648)

注意：i只能循環到N-1（題目要求 ： 至少拆分成 2 個數的和。）