【LeetCode】118、杨辉三角

118、Pascal’s Triangle杨辉三角

难度：简单

题目描述

• 英文：

  Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

• 中文：

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

  

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

• 示例

  Example:

  Input: 5
  Output:
  [
       [1],
      [1,1],
     [1,2,1],
    [1,3,3,1],
   [1,4,6,4,1]
  ]

解题思路

思路一

进行Recursion探索时完成的，其他解法后续补充。

递归关系

我们从定义杨辉三角的递归关系开始。

首先，定义函数$f(i,j)$，表示杨辉三角中第$i$行$j$列的值，之后可以将递归关系表示如下：

$$f(i,j)=f(i-1,j-1)+f(i-1,j)$$

基本情况

在杨辉三角中，每行的最左和最右数字是这个问题的基本情况，值总是为1.

所以，我们可以定义基本情况如下：

$$f(i,j)=1\qquad where\qquad j=1\ or\ j=i$$

代码没有完全对应Recursion相应位置的方法，实现过程中，采用自底向上的方法，保存计算过的中间结果，避免了重复计算。

代码提交

C++，用时4ms，内存8.8M

class Solution {
public:    
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result;
        if (numRows <= 0)
            return result;
        vector<int> temp;
        if (numRows == 1) {
            temp.push_back(1);
            result.push_back(temp);
            return result;
        }

        temp.push_back(1);
        result.push_back(temp);
        for (int row = 1; row < numRows; row++) {
            temp.clear();
            for (int col = 0; col <= row; col++) {
                if (col == 0 || col == row) {
                    temp.push_back(1);
                }
                else {
                    temp.push_back(result[row - 1][col - 1] + result[row - 1][col]);
                }
            }
            result.push_back(temp);
        }
        return result;
    }
};