NYOJ 176 整數劃分（二） （dp）

整數劃分（二）

時間限制： 1000 ms  |  記憶體限制： 65535 KB 難度： 3

描述

把一個正整數m分成n個正整數的和，有多少種分法？

例：把5分成3個正正數的和，有兩種分法：

1 1 3

1 2 2

輸入

第一行是一個整數T表示共有T組測試資料(T<=50)

每組測試資料都是兩個正整數m,n，其中(1<=n<=m<=100),分别表示要拆分的正數和拆分的正整數的個數。

輸出

輸出拆分的方法的數目。

樣例輸入

2
5 2
5 3      

樣例輸出

2
2      

i表示數字大小，j表示拆分成幾個數的和

對于dp[i][j]表示将i分成j個整數有幾種方案；

dp[i-1][j-1],将i分出一個1放在組合的第一位，後面的方案和[i-1][j-1]相同

dp[i-j][j],此時的是非1的情況，即j個整數中都沒有1的存在，此時{x1,x2...xj},一共j個元素;

看起來無從下手，但是，如果我把其中的每一個元素都減1，此時恰好方案和[i-j][j]的方案相同

由此得出公式：

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

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;

int main()
{
    int dp[105][105]= {1};
    for(int i=1; i<=100; i++)
    {
        for(int j=1; j<=i; j++)
        {
            dp[i][j]=dp[i-1][j-1]+dp[i-j][j];
        }
    }
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        printf("%d\n",dp[n][m]);
    }
}