程序填空题：求解整数拆分问题（备忘录法）

求解整数拆分问题。求将正整数n无序拆分成最大数为k（称为n的k拆分）的拆分方案个数，要求所有的拆分方案不重复。

```c++
//求解整数拆分问题的算法
#include
#include
#include
#define MAXN 500
using namespace std;

int dp[MAXN][MAXN];
int dpf(int n,int k)
{
if (@@[dp[n][k]!=0](2)) return dp[n][k];
if (n==1 || k==1)
{
@@[dp[n][k]=1](2);
return dp[n][k];
}
else if (n {
dp[n][k]=@@[dpf(n,n)](2);
return dp[n][k];
}
else if (n==k)
{
dp[n][k]=@@[dpf(n,k-1)+1](2);
return dp[n][k];
}
else
{
dp[n][k]=@@[dpf(n,k-1)+dpf(n-k,k)](2);
return dp[n][k];
}
}
int main()
{
int n,k;
cin>>n>>k;
memset(dp,0,sizeof(dp)); //初始化为0
cout< return 0;
}
```
### 输入格式:

第一个为正整数n，第二个数为拆分最大数k。

```in
5 5
```

### 输出格式:

输出拆分方案数。

```out
7
```







答案：
第1空：dp[n][k]!=0

第2空：dp[n][k]=1

第3空：dpf(n,n)

第4空：dpf(n,k-1)+1

第5空：dpf(n,k-1)+dpf(n-k,k)