解题思路
本题等价于把正整数 n 划分为恰好 k 个正整数的有序序列。直接的划分型动态规划如下：
设 dp[s][t] 表示用恰好 t 枚硬币，面额之和为 s 的有序方案数。
转移时，最后一枚硬币取值为 x (1 ≤ x ≤ s)，那么前面 t-1 枚的和是 s-x，于是：
dp[s][t]=x=1∑sdp[s−x][t−1]
P3900.兑换硬币
题面描述
给定两个正整数 n,k。你有面额为 1,2,3,…,109 的硬币，每种面额数量无限。你必须恰好选出 k 枚硬币，并且要求它们的总面额之和为 n。
选择的顺序不同视为不同方案（如 2,1 与 1,2 记为两种）。求满足条件的方案数；
输入输出
输入：
一行两个整数 n,k。
输出：
输出一个整数，表示恰好用 k 枚硬币凑成面额 n 的方案数。
数据范围
- 1≤n≤63
- 1≤k≤n
样例
输入
3 2
输出
2
说明
可行序列：1,2，2,1。
输入
4 3
输出
3
说明
可行序列：1,1,2，1,2,1，2,1,1。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
