/*
* @lc app=leetcode.cn id=118 lang=c
*
* [118] 杨辉三角
*
* https://leetcode-cn.com/problems/pascals-triangle/description/
*
* algorithms
* Easy (60.22%)
* Total Accepted: 17.6K
* Total Submissions: 29.2K
* Testcase Example: '5'
*
* 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
*
*
*
* 在杨辉三角中，每个数是它左上方和右上方的数的和。
*
* 示例:
*
* 输入: 5
* 输出:
* [
* [1],
* [1,1], 0
* [1,2,1],
* [1,3,3,1],
* [1,4,6,4,1]
* ]
*
*/
/**
* Return an array of arrays.
* The sizes of the arrays are returned as *columnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** generate(int numRows, int** columnSizes) {
int i,j;
if(numRows == ) return ;
int** Array = (int **)malloc(numRows * sizeof(int *));
*columnSizes = (int *)malloc(numRows * sizeof(int));
for(i = ; i < numRows; i++){
(*columnSizes)[i] = i + ;
Array[i] = (int *)malloc((i + ) * sizeof(int));
for(j = ; j < i + ; j++){
if((j == ) || (j == i))
Array[i][j] = ;
else
Array[i][j] = Array[i - ][j - ] + Array[i - ][j];
}
}
return Array;
}
算法核心是很好理解的。如果是首位或者末位，就等于一。否则的话，等于上一轮中两数之和。 如果当前是a[i][j] 那么就等于 a[i-1][j]+a[i-1][j+1]
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
python：
#
# @lc app=leetcode.cn id=118 lang=python3
#
# [118] 杨辉三角
#
# https://leetcode-cn.com/problems/pascals-triangle/description/
#
# algorithms
# Easy (60.22%)
# Total Accepted: 17.6K
# Total Submissions: 29.2K
# Testcase Example: '5'
#
# 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
#
#
#
# 在杨辉三角中，每个数是它左上方和右上方的数的和。
#
# 示例:
#
# 输入: 5
# 输出:
# [
# [1],
# [1,1],
# [1,2,1],
# [1,3,3,1],
# [1,4,6,4,1]
# ]
#
#
class Solution:
def generate(self, numRows):
result = []
if numRows == 0: return []
for i in range(numRows):
temp = []
for j in range(i + 1):
if j == 0:
temp.append(1)
elif j == i:
temp.append(1)
else:
add = result[i - 1][j - 1] + result[i - 1][j]
temp.append(add)
result.append(temp)
return result