https://leetcode.com/problems/pascals-triangle
容易发现杨辉三角的规律，一个数是头上两个数的和。
我写的答案，申请了含有很多0的数组，比较容易理解，但是空间浪费比较多:
public class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> cell = new ArrayList<>();
int[][] nums = new int[numRows + 1][numRows + 1];
for (int i = 0; i < numRows; i++) {
nums[i][0] = 1;
}
//corner case
if (numRows == 0) return result;
cell.add(1);
result.add(new ArrayList<>(cell));
cell.clear();
for (int i = 0; i < numRows-1; i++) {
cell.add(1);
for (int j = 0; j <= i; j++) {
//第i行j列
nums[i + 1][j + 1] = nums[i][j] + nums[i][j + 1];
cell.add(nums[i + 1][j + 1]);
}
result.add(new ArrayList<>(cell));
cell.clear();
}
return result;
}
}
网上的答案（遇到边界的时候不要急，想清楚），只需要保存上一行的数据：
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> result = new ArrayList<>();
//corner case
if (numRows == 0) return result;
List<Integer> preLine = new ArrayList<>();
//first line
preLine.add(1);
result.add(new ArrayList<>(preLine));
for (int i = 1; i < numRows ; i++) {
List<Integer> currentLine = new ArrayList<>();
currentLine.add(1);
for (int j = 0; j < preLine.size() -1; j++) {
currentLine.add(preLine.get(j) + preLine.get(j+1));
}
//last number
currentLine.add(1);
result.add(currentLine);
preLine = currentLine;
}
return result;
}
