程序填空题：求解整数拆分问题（动态规划法）
求解整数拆分问题。求将正整数n无序拆分成最大数为k（称为n的k拆分）的拆分方案个数，要求所有的拆分方案不重复。
```c++
#include
#include
#define MAXN 500
using namespace std;
int dp[MAXN][MAXN]; //动态规划数组
void Split(int n,int k) //求解算法
{
for (int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
{
if (i==1 || j==1)
@@[dp[i][j]=1](2);
else if (i @@[dp[i][j]=dp[i][i]](2);
else if (i==j)
@@[dp[i][j]=dp[i][j-1]+1](2);
else
dp[i][j]=@@[dp[i][j-1]+dp[i-j][j]](2);
}
}
int main()
{
int n,k;
cin>>n>>k;
Split(n,k);
cout< return 0;
}
```
### 输入格式:
第一个为正整数n，第二个数为拆分最大数k。
```in
5 5
```
### 输出格式:
输出拆分方案数。
```out
7
```
答案：
第1空：dp[i][j]=1
第2空：dp[i][j]=dp[i][i]
第3空：dp[i][j]=dp[i][j-1]+1
第4空：dp[i][j-1]+dp[i-j][j]
```c++
#include
#include
#define MAXN 500
using namespace std;
int dp[MAXN][MAXN]; //动态规划数组
void Split(int n,int k) //求解算法
{
for (int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
{
if (i==1 || j==1)
@@[dp[i][j]=1](2);
else if (i
else if (i==j)
@@[dp[i][j]=dp[i][j-1]+1](2);
else
dp[i][j]=@@[dp[i][j-1]+dp[i-j][j]](2);
}
}
int main()
{
int n,k;
cin>>n>>k;
Split(n,k);
cout<
}
```
### 输入格式:
第一个为正整数n，第二个数为拆分最大数k。
```in
5 5
```
### 输出格式:
输出拆分方案数。
```out
7
```
答案：
第1空：dp[i][j]=1
第2空：dp[i][j]=dp[i][i]
第3空：dp[i][j]=dp[i][j-1]+1
第4空：dp[i][j-1]+dp[i-j][j]
