118. 杨辉三角

本文将会写如下几个部分：

何谓“杨辉三角”
LeetCode第118题题目部分
思路分析
题解

1. 何谓杨辉三角

观察下图：

看看这张图，看出了什么？

我们可以直观地观察到几条规律：

每一行的数字个数与其行号相等。例如，第一行就一个数字，第五行有五个数字。
从第二行起，每个数是它左上方和右上方数字之和。
每一行拿出来都是回文串，即，每一行都是沿中间对称的。整个三角形也是沿中间对称的。

2. LeetCode第118题题目部分

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

示例动图

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pascals-triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

3. 思路分析

以输出n阶杨辉三角为例。

思路1--直观地使用观察出来的规律

只要认清“从第二行起，每个数是它左上方和右上方数字之和”，然后照着这条规律写代码即可。具体操作是：

建立一个 $n \times n$ 的二维数组；
用一个二维循环往里填数字。在每行的首个元素和最后一个元素填上1，然后除首尾以外的元素用上面提到的规律赋值。
此题完成。

具体解释一下上面的第2条操作：

虽然为了填数字建立的二维数组每一行元素的个数都是n，但我们只需要保证不需要的元素不填充即可模拟出自己在纸上画的杨辉三角。也就是说，第一行只填充一个，第二行只填充两个，第三行只填三个。依此类推
其实这是一个Brute-Force的思想。直接用编程语言翻译"从第二行起，每个数是它左上方和右上方数字之和"这一条话，剩下的让计算机去跑就好了。

复杂度是 $O(n^2)$ ，且用了 $O(n)$ 的额外空间。

思路2--纯数学思路

此思想来源于科普中国上的介绍。

看图：

数学表示法

在介绍这种思想前，各位读者要将思想转变为0作为首位开始计数的思想，即：

传统意义上的首行是第0行，传统意义上的第二行是第1行；
在每一行中，第一个数字是第0个，第二个数字是第1个；
依此类推。

然后从图上可以看出，第i行中第j个数字正是 $C_{i}^{j}$ 的值。

所以只需要用二项式系数计算即可。

做完此题后，我们可以发现杨辉三角提示了二项式系数计算的一个递归式： $C_{x}^{y} = C_{x-1}^{y-1} + C_{x-1}^{y}$ 。

思路3--针对思路1的改良

上面两种方法其实还可以进一步改良。

前面已经说过，杨辉三角中，每一行都是回文串，即每一行沿中线对称。那么是不是有一种方法，只求前半部分，然后后半部分就可以自然地求出来了？

答案是有的：只需要循环前一半即可，后半部分对称赋值。举例说明：第5行（以0开始计就是第4行）有5个元素，那么我们只需要对前三个元素进行计算，后两个直接利用回文串性质赋值即可。

4. 题解

题解的顺序对应上面的思路顺序。

思路1 (Java实现)

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>(); // res用于返回结果
        
        int[][] ans = new int[numRows][numRows];
        for(int i = 0; i < numRows; ++i){
            List<Integer> ls = new ArrayList<>();
            for(int j = 0; j <= i; ++j){
                if(j == i || j == 0){ ans[i][j] = 1; }
                else{
                    ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];
                }
                ls.add(ans[i][j]);
            }
            res.add(ls);
        }

        return res;
    }
}

思路2 (Python实现)

import math # 直接引入python中的math库，用于计算阶乘

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = list()
        for i in range(numRows):
            tmp = list()
            for j in range(i + 1):
                posi = math.factorial(i) // (math.factorial(j) * math.factorial(abs(i - j))) # 这里必须用双斜线除号，否则posi会被自动转换为浮点数类型
                tmp.append(posi)
            res.append(tmp)
        return res

思路3 (分别用Java和Python实现)

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();

        for(int i = 0; i < numRows; ++i){
            Integer[] tmp = new Integer[i + 1];
            for(int h = 0; h < i + 1; ++h){ tmp[h] = 1; }
            List<Integer> ls = new ArrayList<>(Arrays.asList(tmp));
            if(i > 0){
                for(int j = 1; j < (i / 2) + 1; ++j){
                    int pos = res.get(i - 1).get(j - 1) + res.get(i - 1).get(j); // 唯一需要注意的点是：
                    ls.set(j, pos); // Java的ArrayList类型不能像C++和Python那样用中括号([ ])访问元素，
                    ls.set(i - j, pos); // 只能用get和set方法来做，所以有点不舒服
                } // 所以这种方法不是很推荐用Java去写
            }
            res.add(ls);            
        }

        return res;
    }
}

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = list()
        for i in range(numRows):
            ls = [1 for _ in range(i + 1)]
            if i > 0:
                for j in range(1, i // 2 + 1): # Python需要注意的是要用//（双斜线）来表示整除
                    ls[j] = res[i - 1][j - 1] + res[i - 1][j]
                    ls[i - j] = ls[j]
            res.append(ls)
        return res

118. 杨辉三角

118. 杨辉三角

1. 何谓杨辉三角

2. LeetCode第118题题目部分

3. 思路分析

思路1--直观地使用观察出来的规律

思路2--纯数学思路

思路3--针对思路1的改良

4. 题解

思路1 (Java实现)

思路2 (Python实现)

思路3 (分别用Java和Python实现)

参考文献