LeetCode 119. Pascal's Triangle II

Posted on | In |
Words count in article: 111 | Reading time ≈ 1

题目

Given a non-negative index k where k ≤ 33, return the k^th index row of the Pascal’s triangle.

Note that the row index starts from 0.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

1
2
Input: 3
Output: [1,3,3,1]

Follow up:

Could you optimize your algorithm to use only O(k) extra space?

思路

DP.

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        res = [1] * (rowIndex+1)
        for i in range(2, rowIndex+1):
            for j in range(i-1, 0, -1):
                res[j] += res[j-1]
        return res