题目描述

输出杨辉三角形第row行的所有数据，如输入：4，则返回：

[1,4,6,4,1]

要求用最多O(k)个空间。

我的解法——DP

两层循环直接搞，转移方程：C[i] = C[i-1] + C[i]
n₂的复杂度。
结果：beat 6%

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        res = [1] * (rowIndex + 1)
        if(rowIndex <= 1):
            return res
        last = 1
        for i in range(2,rowIndex + 1):
            for j in range(1,i):
                temp = res[j]
                res[j] = last + res[j]
                last = temp
        return res

最优解法——巧妙的DP

最好的解法
两层循环
n₂的复杂度。

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> A(rowIndex+1, 0);
        A[0] = 1;
        for(int i=1; i<rowIndex+1; i++)
            for(int j=i; j>=1; j--)
                A[j] += A[j-1];  //这里不用倒腾了，6666666666666666666
        return A;
    }
};