119: Pascal’s Triangle II

给定一个非负整数k, 返回第k行的帕斯卡三角的值，可否使用O(k)的空间做到？注意第一行的时候k=0.

思路：帕斯卡三角的每一行都可以由上一行计算得到，利用这个性质，从第一行逐行计算到第k行, 由于
所有的结果都保存在一行，为了使新计算的当前行的数据不影响上一行的数据，可以对每一行从后往前计算
对当前行的索引i上的值l[i], 等于上一行的l[i] + l[i-1]

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        # 6 star, 没理解
        result = [0] * (rowIndex + 1)
        result[0] = 1
        for i in range(1, rowIndex + 1):
            for j in range(i, 0, -1):
                result[j] += result[j-1]
        return result

Go:

1
2
3
4
5
6
7
8
9
10
func getRow(rowIndex int) []int {
    ret := make([]int, rowIndex+1)
    ret[0] = 1
    for i:=1; i < rowIndex+1; i++ {
        for j := i; j >0; j-- {
            ret[j] += ret[j-1]    
        }
    }
    return ret
}