动态规划攻略之：杨辉三角

发表于

「这是我参与11月更文挑战的第16天，活动详情查看：2021最后一次更文挑战」

题目

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

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

image

示例1：

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

示例2：

输入: numRows = 1
输出: [[1]]

解题思路

根据题意可知，杨辉三角具有以下的特性：

  1. 每行数字左右对称，由 1 开始逐渐变大再变小，并最终回到 1。
  2. 每个数字等于上一行的左右俩个数字之和，即第 n 行的第 i 个数等于第 n-1 行的第 i-1 个数和第 i 个数之和。

由此，我们可以一行一行地计算杨辉三角。每当我们计算出第 i 行的值，我们就可以在线性时间复杂度内计算出第 i+1 行的值。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
java复制代码class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> nums = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; j++){
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(nums.get(i-1).get(j-1) + nums.get(i-1).get(j));
                }
            }
            nums.add(row);
        }
        return nums;
    }
}

最后

时间复杂度：O(n2)，n 为行数；
空间复杂度：O(n2);

往期文章：

请你喝杯 ☕️ 点赞 + 关注哦～

  1. 阅读完记得给我点个赞哦，有👍 有动力
  2. 关注公众号— HelloWorld杰少，第一时间推送新姿势

最后，创作不易，如果对大家有所帮助，希望大家点赞支持，有什么问题也可以在评论区里讨论😄～

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%