解题思路
把问题看成把正整数 n 划分成若干个正整数的有序序列。设 dp[s] 表示“按顺序凑成和为 s 的方案数”。最后一枚硬币面额取 x (1 ≤ x ≤ s)，前面部分就必须凑成 s-x，于是有转移：
dp[s]=x=1∑sdp[s−x]
边界为 dp[0] = 1（和为 0 的空序列仅 1 种）。依次从小到大计算 s = 1..n 即可。
P3890.兑换硬币(完全版)
题面描述
给定一个正整数 n。你拥有面额为 1,2,3,…,109 的硬币，每种面额的硬币数量都无限。求有多少种方式使所选硬币的总面额恰好为 n。
注意： 选择的顺序不同视为不同方案（例如 2,1 与 1,2 记为两种）。
输入输出
输入：
一行一个整数 n。
输出：
一行输出一个整数，表示组成面额 n 的方案数。
数据范围
- 1≤n≤63
样例
输入
2
输出
2
说明
可行方案：1,1；2。
输入
3
输出
4
说明
可行方案：1,1,1；2,1；1,2；3。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
