组合数计算中：普通二维数组 vs 滚动一维数组

? 小标题：组合数是怎么算出来的？

组合数 C(n, r) 表示：

从 n 个小球里选出 r 个的方法总数。

有个经典公式：

C(n,r)=C(n−1,r)+C(n−1,r−1)

? 方法一：使用二维表（普通方法）

想象用一个表格保存所有组合数：

? 空间复杂度：O(n²)
要保存整个表格，每一行都占内存。

? 方法二：滚动一维数组（节省空间）

发现：
只要上一行的数据，就能推出当前这一行！

所以只需要一个数组，比如：

C[0] = 1
for (int i = 1; i <= n; i++)
  for (int j = i; j >= 1; j--)
    C[j] = C[j] + C[j - 1];

? 重点：从后往前更新，避免覆盖原值。

? 图解比较：二维 vs 一维

? 普通二维表（全部保存）

每一行都保存：
C[0][0], C[1][0], C[1][1], C[2][0], C[2][1], C[2][2], ...

✅ 结构清晰
❌ 内存开销大（空间复杂度 O(n²)）

? 滚动一维数组（节省内存）

只保留一行：
C[0], C[1], ..., C[n]
每一轮从后往前更新：
C[j] = C[j] + C[j - 1]

✅ 空间只用 O(n)
✅ 算得更快、可算更大
❌ 无法保存所有中间值（不适合做表格）

? 适用场景对比

? 总结一句话

滚动数组就像「踩着自己脚印前进」，一边走一边擦掉过去的路，节省空间还能继续前行！