每日一道算法之--杨辉三角

动态规划递归

Word count: 1kReading time: 4 min

 2020/05/08   Share

杨辉三角

力扣第118题 : https://leetcode-cn.com/problems/pascals-triangle/

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

示例:

输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

1. 迭代实现

首先考虑边界numRows为0时，直接返回一个空列表；
如果numRows不为空时，它的第一个子列表必为[1],所以可以初始化res为[[1]];
每一个子列表的结果,都是上一个子列表从第二个元素开始两两相加(到最后一个元素时不用相加)

具体代码如下:

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 0:
            return []
        res = [[1]]
        for i in range(1, numRows):
            # 前一行从第二位开始相加，最后一个元素单独作为结果
            new_list = [1] + [sum(res[-1][j:j + 2]) for j in range(i)]
            res.append(new_list)
        return res

2. 动态规划

初始化结果数组，numRowsnumRows表示结果数组dpdp的行数，每一行的元素个数等于所处第几行。全部初始化为0
将边界全部初始化为1
遍历dpdp，将为00的位置使用动态规划填入，公式：dp[i][j]=dp[i-1][j-1]+dp[i-1][j]dp[i][j]=dp[i−1][j−1]+dp[i−1][j]

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        dp=[[0]*n for n in range(1,numRows+1)]
        for i in range(numRows):
            dp[i][0]=dp[i][-1]=1
        for i in range(0,numRows):
            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

3. 取巧解法：错一位再逐个相加，28ms/12.5MB

参考自
作者：lu-cheng-5
链接：https://leetcode-cn.com/problems/pascals-triangle/solution/qu-qiao-jie-fa-cuo-yi-wei-zai-zhu-ge-xiang-jia-28m/

观察一下规律，发现当前一行只比上一行多了一个元素，最最关键的一点：本行元素等于上一行元素往后错一位再逐个相加：

因此我们只要对最后一行单独处理：最后一行首、尾分别添加一个零然后对应位置求和就可以得到新的一行

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 0: return []
        res = [[1]]
        while len(res) < numRows:
            newRow = [a+b for a, b in zip([0]+res[-1], res[-1]+[0])]
            res.append(newRow)
        return res

杨辉三角II

力扣第119题 : https://leetcode-cn.com/problems/pascals-triangle-ii/

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

示例:

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

进阶：

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

1. 利用杨辉三角的解法

求到杨辉三角后,返回最后一行的数据即可,但是这样做空间复杂度不为O(k).


class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        res = [[1]]
        for i in range(1, rowIndex + 1):
            # 前一行从第二位开始相加，最后一个元素单独作为结果
            new_list = [1] + [sum(res[-1][j:j + 2]) for j in range(i)]
            res.append(new_list)
        return res[-1]

2. 动态规划

在杨辉三角的题目中,我们是保留了所有的可能性,而这道题目,我们只需要保留一行数据,所以可以在这一个方面进行优化.


class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if(rowIndex==0):
            return [1]
        res = [1,1]
        # 从第三行开始才有计算
        for i in range(3, rowIndex + 2):
            cur = [0] * i
            cur[0] = cur[-1] = 1
            for j in range(1, i-1):
                cur[j] = res[j - 1] + res[j]
            res = cur
        return res

3. 高端解法

作者：leicj
链接：https://leetcode-cn.com/problems/pascals-triangle-ii/solution/python3-yang-hui-san-jiao-ii-by-leicj/


def getRow(rowIndex):
    # j行的数据, 应该由j - 1行的数据计算出来.
    # 假设j - 1行为[1,3,3,1], 那么我们前面插入一个0(j行的数据会比j-1行多一个),
    # 然后执行相加[0+1,1+3,3+3,3+1,1] = [1,4,6,4,1], 最后一个1保留即可.
    r = [1]
    for i in range(1, rowIndex + 1):
        r.insert(0, 0)
        # 因为i行的数据长度为i+1, 所以j+1不会越界, 并且最后一个1不会被修改.
        for j in range(i):
            r[j] = r[j] + r[j + 1]
    return r

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/05/08/algorithm-118/

发表日期：May 8th 2020, 9:57:44 am

更新日期：May 9th 2020, 11:35:38 am

Next Post

每日一道算法之--在 D 天内送达包裹的能力
Previous Post

每日一道算法之--删除排序链表中的重复元素 II

CATALOG

1. 杨辉三角
2. 杨辉三角II

