LeetCode动态规划篇：119.杨辉三角 II

系统管理员 2022-08-30 04:04 136阅读 0赞

![Chris的算法小记][Chris]

我的公众号**Chris的算法小记**，专注于算法、数据结构以及LeetCode题，希望我能写很多通俗易懂的文章，然后大家一起共同成长，一起进步。

一、题目

--------------------

链接：https://leetcode-cn.com/problems/pascals-triangle-ii/

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
    
    在杨辉三角中，每个数是它左上方和右上方的数的和。
    
    示例:
    
    输入: 3
    输出: [1,3,3,1]
    进阶：你可以优化你的算法到 O(k) 空间复杂度吗？

## 二、题解 ##

### 2.1 动态规划 ###

《杨辉三角 II》的思路和《杨辉三角》的思路是一样的，不同是《杨辉三角》需要把结果全部取出来，而《杨辉三角 II》只取固定的行。

具体思路和解法请点击这里噢： [LeetCode动态规划：118.杨辉三角][LeetCode_118.]

但是因为上述解法的时间复杂度和空间复杂度都是 O(n^2)，所以我们可以优化一下。

Python：

class Solution:
        def getRow(self, rowIndex: int) -> List[int]:
            dp=[[0]* i for i in range(1,rowIndex+2)] # 注意：这里是 rowIndex+2 噢。
            for i in range(rowIndex+1):
                dp[i][0]=dp[i][-1]=1
            for i in range(rowIndex+1):
                for j in range(i+1):
                    if dp[i][j]==0:
                        dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
            return dp[rowIndex]

### 2.2 动态规划优化 ###

当前行第 index 项的计算只与上一行第 index-1 项及第 index 项有关。

时间复杂度：O(n^2)

空间复杂度：O(n)

Python:

class Solution:
        def getRow(self, rowIndex: int) -> List[int]:
            dp = [1] * (rowIndex+1)
            for i in range(2, rowIndex+1):
                for j in range(1, i):
                    index = i-j
                    dp[index] = dp[index] + dp[index-1]
            return dp

Go:

func getRow(rowIndex int) []int {
        dp:=make([]int,rowIndex+1)
        dp[0]=1
        for i:=1;i<=rowIndex;i++{
            for j:=i;j>0;j--{
                dp[j]+=dp[j-1]
            }
        }
        return dp
    }

![Chris的算法小记][Chris]

我的公众号**Chris的算法小记**，专注于算法、数据结构以及LeetCode题，希望我能写很多通俗易懂的文章，然后大家一起共同成长，一起进步。如果大家觉得文章不错，可以关注下我噢，会定期分享的。

[Chris]: /images/20220829/b668bd9d9ea14c14ad76340189c25d38.png
[LeetCode_118.]: https://mp.weixin.qq.com/s?__biz=MzI3NTAxMzcxMg==&mid=2247484227&idx=1&sn=597547f0d93739b89232791ef3fbf58f&scene=21#wechat_redirect