杨辉三角第 k 行第 i 到 j 列的和

题目描述

给定杨辉三角的行号 k 和列区间 [i, j]（行列均从 0 开始），求第 k 行第 i 列到第 j 列的元素之和。

数据范围：

• 0 <= k
• 0 <= i <= j <= k

核心思路

1. 杨辉三角与组合数的关系

杨辉三角第 k 行第 c 列的元素，恰好是组合数：

$$C(k, c) = \binom{k}{c}$$

所以第 k 行第 i 列到第 j 列的和为：

$$\sum_{c=i}^{j} \binom{k}{c}$$

2. 为什么用递推而不是直接算阶乘

直接算 $\binom{k}{c} = \frac{k!}{c!(k-c)!}$ 每次都要算阶乘，效率低，而且大数阶乘很慢。

利用组合数的递推关系：

$$\binom{k}{c+1} = \binom{k}{c} \cdot \frac{k - c}{c + 1}$$

从 $\binom{k}{0} = 1$ 出发，可以 $O(1)$ 时间依次算出 $\binom{k}{1}, \binom{k}{2}, \dots$，总体 $O(j)$ 时间，且不需要预计算阶乘。

注意整除顺序：comb * (k - c) // (c + 1) 一定整除，因为 $\binom{k}{c+1}$ 是整数。先乘后除，避免中间结果丢失精度。

3. 算法流程

1. 初始化 comb = 1（即 $\binom{k}{0}$），ans = 0；
2. 对 c 从 0 到 j：
   • 若 c >= i，把 comb 累加到 ans；
   • 更新 comb = comb * (k - c) // (c + 1)，即 $\binom{k}{c+1}$；
3. 返回 ans。

代码实现

行列从 0 开始

def yanghui_row_sum(k: int, i: int, j: int) -> int:
    ans = 0
    comb = 1 
    for c in range(j + 1):
        if c >= i:
            ans += comb
        if c < j:
            comb = comb * (k - c) // (c + 1)
    return ans

复杂度分析

• 时间复杂度：$O(j)$，从 0 遍历到 j。
• 空间复杂度：$O(1)$，只用常数个变量。

Python 整数自动支持大数，结果多大都不会溢出。

关键细节

1. 整除顺序

comb = comb * (k - c) // (c + 1)

必须先乘后除：

• 先乘：comb * (k - c) 保证能被 (c + 1) 整除；
• 后除：// 整数除法。

如果写成 comb * ((k - c) // (c + 1))，可能因 (k - c) 不能整除 (c + 1) 而丢失精度，结果错误。

2. 与「杨辉三角第 k 行和」的关系

如果 i = 0, j = k，即求整行和：

$$\sum_{c=0}^{k} \binom{k}{c} = 2^k$$

可以用快速幂直接算，但本题求任意区间和，没有简单封闭公式，只能用递推。

总结

• 本质：杨辉三角第 k 行第 c 列 = $\binom{k}{c}$，求区间和即求组合数区间和；
• 组合数递推：$\binom{k}{c+1} = \binom{k}{c} \cdot \frac{k - c}{c + 1}$，$O(1)$ 时间更新；
• 算法流程：从 $\binom{k}{0} = 1$ 出发，依次递推，只累加 [i, j] 区间的值；
• 时间 $O(j)$，空间 $O(1)$；
• 易错点：先乘后除，避免整除丢精度；边界截断 i、j；
• 通用套路：「组合数区间和」→ 递推计算组合数，避免阶乘。

相关题目

• LC 118. 杨辉三角（生成前 n 行）
• LC 119. 杨辉三角 II（只生成第 k 行）
• LC 62. 不同路径（组合数应用）