组合数

数学与数论

说明

用帕斯卡递推 C(n,k)=C(n−1,k−1)+C(n−1,k)；空间 O(k)。

分析

组合数满足帕斯卡恒等式：选择某元素或不选它，得到相邻两项之和。用一维数组倒序更新，避免本轮新值覆盖还需要读取的上一轮状态。

图解推演

从 5 个元素选 2 个，按是否选择最后一个元素分成 C(4,1)=4 与 C(4,2)=6，两类无交集且覆盖所有方案，所以结果 10。dp[0]=1 表示空选法；倒序更新才能保持右侧仍来自上一行，正序会错误混入当前行。

查看图表代码

适用前提与边界

结果增长很快，n 较大时 Go int 会溢出。

示例输入与调用

fmt.Println(Choose(5, 2))

运行输出

10

完整 Go 示例

package main

import "fmt"

func Choose(n, k int) int {
	if k < 0 || k > n {
		return 0
	}
	dp := make([]int, k+1)
	dp[0] = 1
	for i := 1; i <= n; i++ {
		for j := min(i, k); j >= 1; j-- {
			dp[j] += dp[j-1]
		}
	}
	return dp[k]
}

func main() {
	fmt.Println(Choose(5, 2))
}