描述
將正整數(shù)n 表示成一系列正整數(shù)之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。 正整數(shù)n 的這種表示稱為正整數(shù)n 的劃分。
輸入
標準的輸入包含若干組測試數(shù)據(jù)。每組測試數(shù)據(jù)是一行輸入數(shù)據(jù),包括兩個整數(shù)N 和 K。 (0 < N <= 50, 0 < K <= N)
輸出
對于每組測試數(shù)據(jù)，輸出以下三行數(shù)據(jù): 第一行: N劃分成K個正整數(shù)之和的劃分數(shù)目 第二行: N劃分成若干個不同正整數(shù)之和的劃分數(shù)目 第三行: N劃分成若干個奇正整數(shù)之和的劃分數(shù)目
樣例輸入
5 2
樣例輸出
2 3 3
提示 第一行: 4+1, 3+2, 第二行: 5，4+1，3+2 第三行: 5，1+1+3， 1+1+1+1+1+1
分析
整數(shù)劃分問題這幾個變形確實很經(jīng)典，需要一個個說明下： 設dp[n][m]表示數(shù)n劃分方案中，每個數(shù) 不大于m 的劃分數(shù)。
N劃分成若干個可相同正整數(shù)之和
劃分分兩種情況：
劃分中每個數(shù)都小于m：則劃分數(shù)為dp[n][m-1]。劃分中至少有一個數(shù)等于m：則從n中減去去m，然后從n-m中再劃分，則劃分數(shù)為dp[n-m][m]。動態(tài)轉(zhuǎn)移方程：dp[n][m]=dp[n][m-1]+dp[n-m][m]。
N劃分成若干個不同正整數(shù)之和
劃分分兩種情況：
劃分中每個數(shù)都小于m：則劃分數(shù)為dp[n][m-1]。劃分中至少有一個數(shù)等于m：則從n中減去m，然后從n-m中再劃分，且再劃分的數(shù)中每個數(shù)要小于m, 則劃分數(shù)為dp[n-m][m-1]。動態(tài)轉(zhuǎn)移方程：dp[n][m]=dp[n][m-1]+dp[n-m][m-1]。
N劃分成K個正整數(shù)之和
設dp[n][k]表示數(shù)n劃分成k個正整數(shù)之和時的劃分數(shù)。 劃分分兩種情況：
劃分中不包含1：則要求每個數(shù)都大于1，可以先拿出k個1分到每一份，之后在n-k中再劃分k份，即dp[n-k][k]。劃分中包含1：則從n中減去1，然后從n-1中再劃分k-1份, 則劃分數(shù)為dp[n-1][k-1]。動態(tài)轉(zhuǎn)移方程：dp[n][k]=dp[n-k][k]+dp[n-1][k-1]。
N劃分成若干個奇正整數(shù)之和
設f[i][j]表示將數(shù)i分成j個正奇數(shù)，g[i][j]表示將數(shù)i分成j個正偶數(shù)。 首先如果先給j個劃分每個分個1，因為奇數(shù)加1即為偶數(shù)，所以可得： f[i-j][j] = g[i][j]。 劃分分兩種情況：
劃分中不包含1：則要求每個數(shù)都大于1，可以先拿出k個1分到每一份，剛可將問題轉(zhuǎn)換為”從i-j中劃分j個偶數(shù)”，即g[i-j][j]。劃分中包含1：則從n中減去1，然后從n-1中再劃分k-1份, 則劃分數(shù)為dp[n-1][k-1]。動態(tài)轉(zhuǎn)移方程：f[i][j]=f[i-1][j-1]+g[i-j][j]。
實現(xiàn)
#include <iostream>#include <cstring>using namespace std;#define N 51int dp1[N][N]; //N劃分成K個正整數(shù)之和的劃分數(shù)目。int dp2[N][N]; //N劃分成若干個不同正整數(shù)之和的劃分數(shù)目。int dp3[N][N]; //N劃分成若干個可相同的正整數(shù)之和的劃分數(shù)目。int f[N][N]; //N劃分成K個奇正整數(shù)之和的劃分數(shù)目。int g[N][N]; //N劃分成K個偶正整數(shù)之和的劃分數(shù)目。void initDivideInt() { memset(dp1, 0, sizeof(dp1)); //dp[n][k]=dp[n-k][k]+dp[n-1][k-1] memset(dp2, 0, sizeof(dp2)); //dp[n][m]=dp[n][m-1]+dp[n-m][m-1] memset(dp3, 0, sizeof(dp3)); //dp[n][m]=dp[n][m-1]+dp[n-m][m] for (int i = 1; i < N; i++) { for (int j = 1; j < N; j++) { if (i < j) { dp1[i][j] = 0; dp2[i][j] = dp2[i][i]; dp3[i][j] = dp3[i][i]; } else if (i == j) { dp1[i][j] = 1; dp2[i][j] = dp2[i][j - 1] + 1; dp3[i][j] = dp3[i][j - 1] + 1; } else { dp1[i][j] = dp1[i - j][j] + dp1[i - 1][j - 1]; dp2[i][j] = dp2[i][j - 1] + dp2[i - j][j - 1]; dp3[i][j] = dp3[i][j - 1] + dp3[i - j][j]; } } }}//f[i][j]=f[i-1][j-1]+g[i-j][j]void initDivideOdd() { f[0][0] = 1; g[0][0] = 1; for (int i = 1; i < N; i++) { for (int j = 1; j <= i; j++) { g[i][j] = f[i - j][j]; f[i][j] = f[i - 1][j - 1] + g[i - j][j]; } }}int main() {// freopen("in.txt", "r", stdin); int n, k; initDivideInt(); initDivideOdd(); while (cin >> n >> k) { cout << dp1[n][k] << endl; cout << dp2[n][n] << endl; int sum = 0; for (int i = 0; i <= n; i++) { sum += f[n][i]; } cout << sum << endl; } return 0;}
