119. Pascal's Triangle II

#Problem

Given an integer rowIndex, return the rowIndexᵗʰ (0-indexed) row of the Pascal’s triangle.

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

https://leetcode.cn/problems/pascals-triangle-ii/

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

Constraints:

• 0 <= rowIndex <= 33

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

#Test Cases

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:

import pytest

from solution import Solution


@pytest.mark.parametrize('rowIndex, expected', [
    (3, [1,3,3,1]),
    (0, [1]),
    (1, [1,1]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, rowIndex, expected):
    assert sol.getRow(rowIndex) == expected

#Thoughts

杨辉三角的的每个数字都是一个组合数，第 n（0-indexed）行第 m（0-indexed）个数字的值为 $\binom{n}{m}=\frac{n!}{m!(n-m)!}$。

因为要输出一整行，还可以看一下同一行前后数字的递推关系，易知

这样就可以从第一个数（1）依次递推出整个数组。另外因为对称性，有 $\binom{n}{m}=\binom{n}{n-m}$，只需要计算前半个数组，后边个数组直接根据对称性填充即可。

时间复杂度 O(n)，附加的空间复杂度 O(1)。

#Code

class Solution:
    def getRow(self, rowIndex: int) -> list[int]:
        n = rowIndex
        res = [1] * (n + 1)
        for m in range(1, n // 2 + 1):
            res[m] = res[n - m] = res[m - 1] * (n - m + 1) // m

        return res