整數劃分模型

整數劃分模型

\(n\) 個數劃分成 \(k\) 個的方案數

狀态 \(f[i][j]\) 表示 将\(i\)劃分為\(j\)的方案數

對于方案數，一般是由地推式子推的，

對于我們考慮最後一個盒子放的數為 \(1\) 或 \(!1\)，

那麼最後一個數為 \(1\) 時，由于是第 \(j\) 列，那麼他的方案數就是 \(j-1\)列的方案數，目前這一列就放一個，對于前面的方案數不受影響

即\(f[i-1][j-1]\)

當最後一位數是非 \(1\)時，\(1-j\) 每個數至少大于 \(1\)，如果将每個數都減一，方案數變嗎，答案是不變

因為對于每種可能，\(1-j\) 上的數都是大于 \(1\) 的，那麼減一并不會影響劃分

\(f[i-j][j]\)

是以轉移時為\(f[i][j]=f[i-1][j-1]+f[i-j][j]\)

\(n\) 個數劃分成 \(k\) 個不相同的數的方案數

考慮最後一位為 \(1\) 的情況

上一個是 \(f[i-1][j-1]\) ，假若這個式子的方案數中有存在相同的 \(1\)，是不符合條件的

有第一個題的第二中情況同理可知

\(dp[i-j][j]\)可以轉移答案，我令\(j=j-1\) ，那麼式子成為 \(f[i-(j-1)][j-1]\), 前\(j-1\)的方案數是這個，那到\(j\)上就一個 \(1\)不會差生影響，就是從\(i\)拿個1而已

則有\(f[i-1-(j-1)][j]=f[i-j][j]\),注意這的第二唯，因為後面多了一個方一的盒子，是以\(j-1\)變成了\(j-1+1\)

為什麼這樣就沒有重複的 \(1\) 呢，

因為這個式子(第一問第二種請狂)的原型是 \(f[i-j][j]\) 他是什麼情況？，每一列上的數都是大于\(1\)的，我隻不過最後面多加一個盒子（j+1），裡面剛好放的是 \(1\)而已，前面的 \(j\)的盒子的數有\(1\)嗎

是以式子為\(f[i][j]=f[i-j][j-1]+f[i-j][j]\)

就會這兩個（逃