杨辉三角

末蓝、 2022-12-26 15:26 312阅读 0赞

### 一、什么是杨辉三角 ###

> **杨辉三角**：是**二项式系数**在三角形中的一种几何排列。  
> 杨辉三角的每个数等于它上方两数之和。  
> ![在这里插入图片描述][20201206114053340.gif]

### 二、求杨辉三角第n行 ###

> 杨辉三角第n行第m个数的值为组合数  C n − 1 m − 1 C\_\{n-1\}^\{m-1\} Cn−1m−1 的结果

1.  代码
    
    > [leetcode 119题 杨辉三角Ⅱ][leetcode 119_]
    
        /** * @param {number} rowIndex * @return {number[]} */
        var getRow = function(rowIndex) { 
            /** * 数学法 * 杨辉三角第n行第m项 = C(n-1, m-1)的组合数 * 时间复杂度：O(n) * 空间复杂度：O(n) 存储结果 */
            // 预处理（无）
        
            // 组合数计算函数
            function c(_base, _select){ 
                /** * 组合数计算 * @param { number } _base: 选择基 * @parem { number } _select: 选择数 * @return { number }: 计算 _base 选 _select的组合数 */
                if(_select === 0) return 1;
                return Array.from({ length: _select}, (v, i) => _base - i).reduce((pre, curr) => pre * curr) / Array.from({ length: _select}, (v, i) => i + 1).reduce((pre, curr) => pre * curr);
            }
            
            // 计算第rowIndex+1行的结果
            let result = [];
            // 计算一半结果（杨辉三角每一行延中轴对称）
            let halfLen = Math.ceil((rowIndex+1) / 2);
            for(let i=1; i<=halfLen; i++){ 
                result.push(c(rowIndex, i-1));
            }
            // 对称复制一半结果
            for(let i=0; i<halfLen; i++){ 
                result.push(result[halfLen-1-i]);
            }
            // 当前行有奇数个结果，剔除一个
            ((rowIndex+1) % 2 === 1) && result.splice(halfLen, 1);
            return result;
        };

[20201206114053340.gif]: /images/20221120/9d921cf938e24d19892af2e28a98afdd.png
[leetcode 119_]: https://leetcode-cn.com/problems/pascals-triangle-ii/