119. 杨辉三角 II

Leetcode题目:动态规划

给定一个非负索引 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:
    vector<int> getRow(int rowIndex) {
        vector<vector<int>>result(rowIndex+1);
        for(int i=0;i<=rowIndex;i++)
        {
            result[i].resize(rowIndex+1);
            result[i][0]=result[i][i]=1;
            for(int j=1;j<rowIndex;j++)
            {
                if(i>=2)
                {
                    result[i][j]=result[i-1][j-1]+result[i-1][j];
                }
            }
        }
        return result[rowIndex];
    }
};
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x