蒜头君特别喜欢数学。今天，蒜头君突发奇想：如果想要把一个正整数 nn 分解成不多于 kk 个正整数相加的形式，那么一共有多少种分解的方式呢？

蒜头君觉得这个问题实在是太难了，于是他想让你帮帮忙。

输入格式

共一行，包含两个整数 n(1 \leq n \leq 300)n(1≤n≤300) 和 k(1 \leq k \leq 300)k(1≤k≤300)，含义如题意所示。

输出格式

一个数字，代表所求的方案数。

样例输入#include <stdio.h>

long l
5 3

样例输出

5
#include <stdio.h>
long long  dp[350][350];
int main()
{
long long n , k;
	scanf("%lld %lld" , &n , &k);
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 1 ; j <= k ; j++)
		{
			dp[i][j] = 0;
			dp[i][1] = 1;//将I分成一份 ， 有一种
			dp[1][j] = 1;//将1分成不大于j份 ， 一种
		}
	}
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 1 ; j <= k ; j++)
		{//i < j 时 ， 相当于将i分成i份
			if(i < j )
			{
				dp[i][j] = dp[i][i];
			}

                        //i==j时 ， 分成两种 ， 一种是只由1组成 ，只有一种，另外一种是分成小于j份，即至少有一份是空； 
			else if( i == j)
			{
				dp[i][j] = dp[i][j-1] + 1;
			}
			else//i>j时 ，分成j份和小于j份的情况 

			{
				dp[i][j] = dp[i][j-1] + dp[i-j][j];
			}
		}
	}
printf("%lld\n" , dp[n][k]);
	return 0;
}

整数划分

1.将n分为不大于m的数相加

将 i 分成有 j 和无 j 的情况 (可重复)

dp[i][j] = dp[i-j][j] + dp[i][j-1];(i >= j)

dp[i][j] = dp[i][i](i < j)

将 i 分成有 j 和无 j 的情况 (不重复)
dp[i][j] = dp[i-j][j-1] + dp[i][j-1];(i >= j)
dp[i][j] = dp[i][i](i < j)

2.将n 分为不大于k个数之和

将 i 分成有 1 和无 1 的情况（可重复） 

先将 i 中减去 j 的数量 ， 再平分 j 中， 则为没有1的情况 

留一个为 1 ， 其他的继续分 
dp[i][j] = dp[i-j][j] + dp[i-1][j-1](i >= j)
dp[i][j] = dp[i][i](i < j) 

将 i 分成有 1 和无 1 的情况（不重复） 
dp[i][j] = dp[i-j][j-1] + dp[i-1][j-1](i >= j)
dp[i][j] = dp[i][i](i < j)

3.将i分成若干个奇数之和 

j为奇数时： 

dp[i][j] =  dp[i-j][j] + dp[i][j-1](i <= j)
dp[i][j] = dp[i][i](i < j) 
j为偶数时：
dp[i][j] = dp[i][j-1];