Readme

2221.Find-Triangular-Sum-of-an-Array

本题最直观的方法就是模拟，根据数据规模，N^2的时间复杂度是可以接受的。

本题其实还有另外一个切入的角度。从题目上看，三角形的构造方法与杨辉三角形非常相似，所以此题一定和二项式系数有关。

我们从下往上观察，最后两行是

1     1
   1

这意味着此时最上面一行的每一个元素对于最终结果（即最底角的元素）的贡献是1:1.

再观察最后三行

1  2  1
 1   1
   1

此时发现，最上面一行的每一个元素对于最终结果（即最底角的元素）的贡献恰好就是1:2:1. 究其原因，元素(1,1)会复制给(2,1)，元素(1,2)会复制给(2,1)和(2,2)造成了双倍的贡献，而元素(1,3)又会只贡献给(2,2)。也就是说，我们只需要通过第二行，就可以推出第一行里每个元素对于底角元素的贡献值。

再观察最后四行

1 3  3  1
 1  2  1
  1  1
    1

很明显了，最上面一行的每个元素对于底角元素的贡献值比例1:3:3:1，它就是(a+b)^3的二项式系数，即C(3,0)，C(3,1)，C(3,2)，C(3,3)，其中C(x,y)表示组合数。

于是我们就可以得出结论，令n = nums.size()-1，那么原始数值里的nums[i]，会复制C(n,i)份计入到递交元素中。我们只需要将nums按照n次二项式系数加权平均即可。

计算二项式系数，就是算组合数，可以参考模板代码