解题思路

我们要求从集合 $\{1,2,\ldots,n\}$ 中选出 $k$ 个数的方案数，即组合数 $C(n,k)$。

采用划分型动态规划：按“是否选择元素 $n$”把所有方案划分为两类：

• 不选 $n$：数量为 $C(n-1,k)$；
• 选 $n$：数量为 $C(n-1,k-1)$。 由此得到递推：

题面描述

给定两个整数 $n$ 和 $k$，从集合 $\{1,2,\ldots,n\}$ 中选出 $k$ 个数的所有方案的数量

输入输出

输入： 一行包含两个整数 $n,k$。

输出： 一行输出一个整数，即从 $\{1,2,\ldots,n\}$ 中选出 $k$ 个数的方案数。

数据范围

• $1 \le n \le 30$
• $0 \le k \le n$

样例1

输入

3 2

输出

3

样例2

输入

5 3

输出

10

说明 当 $n=3,k=2$ 时，方案为 $[1,2],[1,3],[2,3]$，共 3 种；