第一題：
1 樣例：如一個正整數5，可以劃分為7種：
[5]
[4,1]
[3,2] [3,1,1]
[2,2,1] [2,1,1,1]
[1,1,1,1,1]
2分析：2
將一個正整數n劃分，共有多少種劃分方式？
上面的例子第一行，所有加數不超過5；
第二行，所有加數不超過4；
........
第五行，所有加數不超過1.
定義 dp[n][m]表示正整數n，所有加數不超過m的劃分數目。
3分析m，n：
1、n== 1或m== 1時共1種劃分方式dp[n][m] = 1;
2、n== m時dp[n][n]= dp[n][m-1]+1，這樣就把主要問題轉化為對3的分解。
3、n> m時我們發現只要將dp[n][m-1]加上包含加數m的劃分數就等於dp[n][m]。即：dp[n][m]= dp[n][m-1] +包含加數m的劃分數。
包含加數m的劃分數可以轉化為：dp[n-m][m]。所以3可以表示為：
dp[n][m]= dp[n][m-1] + dp[n-m][m]
4、n< m等同於dp[n][n];
4代碼：
[cpp] view plaincopy
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1010
int t , k;
int dp[MAXN][MAXN];
void solve(){
memset(dp , 0 , sizeof(dp));
for(int i = 1 ; i <= k ; i++){
for(int j = 1 ; j <= k ; j++){
if(i == 1 || j == 1)
dp[i][j] = 1;
else if(i == j)
dp[i][j] = dp[i][j-1] + 1;
else if(i < j)
dp[i][j] = dp[i][i];
else
dp[i][j] = dp[i][j-1] + dp[i-j][j];
}
}
printf("%d\n" , dp[k][k]);
}
int main(){
scanf("%d" , &t);
while(t--){
scanf("%d" , &k);
solve();
}
return 0;
}
第二題：
1 樣例：5分成2個正整數的和有2種
1 4
2 3
2分析：
定義dp[n][m]表示的是將n分成m部分的方案數，那麼這個時候就考慮這個m部分的組成情況
1如果這m部分沒有1，那麼我們先將m個1分到m份上面，然後在將剩下的n-k分到m部分上，所以就有dp[n][m] = dp[n-m][m];
2如果這m部分有1，那麼先將1這個部分扣除，剩下的就是n-1分給m-1部分了，
所以就有dp[n][m] =dp[n-1][m-1];
所以就有dp[n][m]= dp[n-m][m] + dp[n-1]][m-1]；
3注意事項：
當n= m時候dp[n][m]= 1;
當 m= 1時候dp[n][m]= 1;
當 n= 1時候n< m那麼dp[n][m]= 0；
4代碼：
[cpp] view plaincopy
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110
int t , m , n;
int dp[MAXN][MAXN];
void solve(){
int i , j;
memset(dp , 0 , sizeof(dp));
for(i = 1 ; i <= n ; i++)
dp[i][i] = dp[i][1] = 1;
for(i = 1; i <= n ; i++){
for(j = 1 ; j <= m ; j++){
if(i <= j)
break;
if(i != 1 && j != 1)
dp[i][j] = dp[i-j][j] + dp[i-1][j-1];
}
}
printf("%d\n" , dp[n][m]);
}
int main(){
scanf("%d" , &t);
while(t--){
scanf("%d%d" , &n ,&m);
solve();
}
}
第三題：
1 分析：
第一問：
和第一題相同
第二問：
和第二題相同
第三問：
在第一問的基礎上大答案為dp[n][k];
第四問(不懂為什麼)：
用dp[i][j]表示將i分成j個奇數的方案數，tmpDP[i][j]表示將i分成j個偶數的方案數
那麼就有tmpDP[i][j] = dp[i-j][j]; dp[i][j] = dp[i-1][j-1] + tmpDP[i-j][j];
第五問：
0/1背包的變形，有n件物品大小為1,2......n.求將大小為n的背包裝滿共有幾種方案數。
那麼就有狀態轉移方程： dp[i][j] = dp[i-1][j] + dp[i-1][j-i]; (j >= i)
dp[i][j] = dp[i-1][j] (j < i)
2代碼：
[cpp]
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110
int n , k;
long long dp[MAXN][MAXN];
long long ans;
void solve(){
int i , j;
/*第一個問題dp[i][j]表示將i分成不大於j的方案數*/
memset(dp , 0 , sizeof(dp));
for(i = 1 ; i <= n ; i++){
for(j = 1; j <= n ; j++){
if(i == 1 || j == 1)
dp[i][j] = 1;
else if(i == j)
dp[i][j] = 1 + dp[i][j-1];
else if(i < j)
dp[i][j] = dp[i][i];
else
dp[i][j] = dp[i][j-1] + dp[i-j][j];
}
}
printf("%lld\n" , dp[n][n]);
ans = dp[n][k];/*保存下來作為第三問題的答案*/
/*第二個問題dp[i][j]表示將i分成j部分的方案數*/
memset(dp , 0 , sizeof(dp));
for(i = 1 ; i <= n ; i++)
dp[i][i] = dp[i][1] = 1;
for(i = 1 ; i <= n ; i++){
for(j = 1 ; j <= k ; j++){
if(i <= j)
break;
if(i != 1 && j != 1)
dp[i][j] = dp[i-j][j] + dp[i-1][j-1];
}
}
printf("%lld\n%lld\n" , dp[n][k] , ans);
/*第四個問題（不大懂）*/
long long tmpDP[MAXN][MAXN];
memset(dp , 0 , sizeof(dp));
memset(tmpDP , 0 , sizeof(tmpDP));
dp[0][0] = tmpDP[0][0] = 1;
for(i = 1 ; i <= n ; i++){
for(j = 1 ; j <= i ; j++){
tmpDP[i][j] = dp[i-j][j];
dp[i][j] = dp[i-1][j-1] + tmpDP[i-j][j];
}
}
for(ans = 0 , i = 1 ; i <= n ; i++)
ans += dp[n][i];
printf("%lld\n" , ans);
/*第五個問題dp[i][j]表示前i個物品中組成為j的方案數*/
memset(dp , 0 , sizeof(dp));
for(i = 1 ; i <= n ; i++)
dp[i][0] = dp[i][1] = 1;/*賦值初始化*/
for(i = 1 ; i <= n ; i++){
for(j = n ; j >= 2 ; j--){
if(j >= i) /*j >= i*/
dp[i][j] = dp[i-1][j] + dp[i-1][j-i];
else
dp[i][j] = dp[i-1][j]; /*j < i*/
}
}
printf("%lld\n\n" , dp[n][n]);/*輸出答案*/
}
int main(){
while(scanf("%d%d" , &n , &k) != EOF)
solve();
return 0;
}
