解题思路

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

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

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

边界条件：

• 初始化 $dp[0][0]=1$；
• 对每个 $i=1..n$：先令 $dp[i][0]=1$，再对 $j=1.. \min(i,k)$ 用递推式更新。

复杂度分析

• 时间复杂度：$O(nk)$。
• 空间复杂度：$O(nk)$（使用二维表）。

代码实现

Python

# 功能函数：使用二维 DP 计算组合数 C(n, k)
def count_combinations(n, k):
    # 按题意 k 在 [0, n]，这里仍做保护
    if k < 0 or k > n:
        return 0
    # 构建二维 DP 表，dp[i][j] 表示从 {1..i} 里选 j 个的方案数
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1  # 基础情形

    for i in range(1, n + 1):
        dp[i][0] = 1  # C(i,0)=1
        upper = min(i, k)  # 只有 j<=i 时才有意义
        for j in range(1, upper + 1):
            # 划分：不选 i vs 选 i
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
    return dp[n][k]

# 主函数：读取输入并输出结果（ACM 风格）
def main():
    import sys
    line = sys.stdin.readline().strip()
    n_str, k_str = line.split()  # 输入为两个整数，用空格分隔
    n, k = int(n_str), int(k_str)
    print(count_combinations(n, k))

if __name__ == "__main__":
    main()

Java

import java.util.*;

// ACM 风格主类名要求为 Main
public class Main {
    // 功能函数：二维 DP 计算 C(n, k)
    static long countCombinations(int n, int k) {
        if (k < 0 || k > n) return 0L;
        long[][] dp = new long[n + 1][k + 1];
        dp[0][0] = 1L; // 基础情形

        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1L; // C(i,0)=1
            int upper = Math.min(i, k); // 仅当 j<=i 有意义
            for (int j = 1; j <= upper; j++) {
                // 划分：不选 i vs 选 i
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }
        return dp[n][k];
    }

    // 主函数：读取输入并输出
    public static void main(String[] args) {
        // 数据范围很小，Scanner 足够
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long ans = countCombinations(n, k);
        System.out.println(ans);
        sc.close();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 功能函数：二维 DP 计算 C(n, k)
long long count_combinations(int n, int k) {
    if (k < 0 || k > n) return 0LL;
    // dp[i][j] 表示从 {1..i} 中选 j 个的方案数
    vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0LL));
    dp[0][0] = 1LL; // 基础情形

    for (int i = 1; i <= n; ++i) {
        dp[i][0] = 1LL; // C(i,0)=1
        int upper = min(i, k); // 仅当 j<=i 时有效
        for (int j = 1; j <= upper; ++j) {
            // 划分：不选 i vs 选 i
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
        }
    }
    return dp[n][k];
}

// 主函数：读取输入并输出（ACM 风格）
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    cout << count_combinations(n, k) << "\n";
    return 0;
}

题面描述

给定两个整数 $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 种；