118.E 杨辉三角

Problem: 118. 杨辉三角

思路

动态规划

观察三角形的特征，可以看到首尾位置固定为1，对于中间位置而言，则：

f[i][j] = f[i-1][j-1] + f[i-1][j]

Code

func generate(numRows int) [][]int {
	triangle := make([][]int, numRows)
	for i := 0; i < numRows; i++ {
		triangle[i] = make([]int, i+1)
		triangle[i][0] = 1 //第一个元素置为1
		triangle[i][i] = 1 //最后一个元素置为1
		//填充中间元素
		for j := 1; j < i; j++ {
			triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
		}
	}

	return triangle
}