118md.md

LeetCode 118. Pascal's Triangle

##題目 Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5, Return

  [
       [1],
      [1,1],
     [1,2,1],
    [1,3,3,1],
   [1,4,6,4,1]
  ]

##翻譯 numRows為列數，產生一個Pascal三角形，例如說 numRows = 5 ，產生三角形如上所示。

##思路

1. 每一列第一個值都是1。
2. 每一列第n個值則是上一列n-1位子+n位子的值。
3. 假如是該列最後一個值Nx，前一列沒有Nx這個值，可以視為0。
4. 有了以上規則，要算出毎一列的值就很簡單了，直接看下面程式碼。

##解題

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    if(numRows == 0) return [];
    
    // 放入第一列
    var trigle = [[1]];
    
    for(var i = 1 ; i < numRows ; i++){
        var prevRow = trigle[i-1]; // 前一列
        var curRow  = [1];         // 每一列開始都是1    
        
        for(var j = 1 ; j <= i; j++){
            // 每一列的第n個值都是 前一列pre[n-1] + pre[n]
            var pre =  prevRow[j-1];
            var cur =  prevRow[j] ?  prevRow[j] : 0;
            curRow.push(pre+cur);  
        }
        trigle.push(curRow);
    }
    
    return trigle;
};