119. Pascal's Triangle II

题目

给定一个行号，返回杨辉三角的第 N 行的数列。

解析

如果从空间维度完整构造一个拥有 N 行的杨辉三角，需要 N ! 个存储单位。考虑杨辉三角的特殊性，第 N+1 行的第 I 个元素值为 c(n+1)(i) = c(n)(i-1) + c(n)(i)。
所以考虑从后往前计算新的行。具体的方法时

1. 每次新增一行时，在末尾补 1
2. 计算 i-1 的值并更新，直到首元素不再计算

伪代码

c = [row+1]int
c[0] = 1
for (r = 1; r<=row; r++)
  c[r] = 1
  for(i  = r-1; i > 0; i--)
    c[i] = c[i] + c[i-1]
return c

代码

func getRow(rowIndex int) []int {
    row := rowIndex
    c := make([]int, row+1)
    c[0] = 1
    for r := 1; r <= row; r++ {
        c[r] = 1
        for i := r-1; i > 0; i-- {
            c[i] += c[i-1]
        }
    }
    return c
}

image.png