LeetCode刷题【119】杨辉三角 II

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

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

示例 1:

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

示例 2:

输入: rowIndex = 0
输出: [1]

示例 3:

输入: rowIndex = 1
输出: [1,1]

提示:

• 0 <= rowIndex <= 33

进阶：

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

题解

嗯，依旧明显的动态规划问题，滚动数组实现

class Solution {
    public List<Integer> getRow(int rowIndex) {
        int[][] dp = new int[rowIndex+1][rowIndex+1];
        dp[0][0] = 1;
        int row = 1;
        while (row <= rowIndex){
            for (int i = 0; i <= row; i++) {
                dp[row][i] = i==0?1:dp[row-1][i]+dp[row-1][i-1];
            }
            row++;
        }
        List<Integer> res = new ArrayList<>();
        for (int i : dp[rowIndex]) {
            res.add(i);
        }
        return res;
    }
}

之前的参考LeetCode刷题【118】杨辉三角