119-pascals-triangle-ii.md

119. 杨辉三角 II - easy

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 3
输出: [1,3,3,1]

进阶：

你可以优化你的算法到 O(k) 空间复杂度吗？

thinking

使用 O(k) 空间复杂度，需要从高位往地位计算，因为是上一行的 index 和 index-1 位相加，所以从后往前计算时，需要的信息不会丢失。

code

第一版本以实现为主：

func getRow(rowIndex int) []int {
    var results []int
    for i := 0; i <= rowIndex; i++ {
        vs := make([]int, i+1)
        vs[0], vs[i] = 1, 1
        for j := 1; j < i; j++ {
            vs[j] = results[j-1] + results[j]
        }
        results = vs
    }
    return results
}

优化，使用两个数组滚动：

func getRow(rowIndex int) []int {
    r, c := make([]int, rowIndex+1), make([]int, rowIndex+1)

    for i := 0; i <= rowIndex; i++ {
        c[0], c[i] = 1, 1
        for j := 1; j < i; j++ {
            c[j] = r[j-1] + r[j]
        }
        r, c = c, r
    }
    return r
}

看了题解思路，使用 O(k) 空间复杂度：

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