一本通 1304：数的划分（线性DP）

1 、ans[n][k] 表示n分为k个数相加，有多少种加法
k > n 时候， ans[n][k] = 0
n = 0 或者 k = 0 时候， ans[n][k] = 0
2、 状态转移： ans[n][k] = ans[n - 1][k - 1] + ans[n - k][k]
3、 例子： ans[7][3] = 4,
7 = 1 + 1 + 5 = 1 + 2 + 4 = 1 + 3 + 3 = 2 + 2 + 3
6 = 1 + 5 = 2 + 4 = 3 + 3, 这三张分法，在前面加上1就凑成了 ans[7][3]
的前3 中分法， 而 7 = 2 + 2 + 3， 可以在每一项减1，成了
4 = 1 + 1 + 2, 这个和 7 = 2 + 2 + 3 对应上的，
ans[7][3] = ans[6][2] + ans[7 - 3][3]

#include 
using namespace std;
const int MaxN = 210;
int ans[MaxN][10];	// ans[n][k] 表示n分为k个数相加，有多少种加法
int n, k;

int main()
{
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i)
	{
		ans[i][1] = i;
	}
	for(int i = 2; i <= n; ++i)
	{
		for(int j = 1; j <= k; ++j)
		{
			if(j <= i)
			{
				ans[i][j] = ans[i - 1][j - 1] + ans[i - j][j];	
			}else{
				ans[i][j] = 0;
			}
		}
	}
	printf("%d\n", ans[n][k]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28