解题思路
我们要求从集合 {1,2,…,n} 中选出 k 个数的方案数，即组合数 C(n,k)。
采用划分型动态规划：按“是否选择元素 n”把所有方案划分为两类：
- 不选 n：数量为 C(n−1,k)；
- 选 n：数量为 C(n−1,k−1)。
由此得到递推：
P3860.杨辉三角
题面描述
给定两个整数 n 和 k，从集合 {1,2,…,n} 中选出 k 个数的所有方案的数量
输入输出
输入：
一行包含两个整数 n,k。
输出：
一行输出一个整数，即从 {1,2,…,n} 中选出 k 个数的方案数。
数据范围
- 1≤n≤30
- 0≤k≤n
样例1
输入
3 2
输出
3
样例2
输入
5 3
输出
10
说明
当 n=3,k=2 时，方案为 [1,2],[1,3],[2,3]，共 3 种；
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
