LeetCode82 - 杨辉三角

📝 题目描述

题目链接：杨辉三角

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

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

示例：

示例 1:

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

示例 2:

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

提示：

• 1 <= numRows <= 30

💡 解题思路

方法一：动态规划

杨辉三角的每一行的每个数字，等于上一行的左右两个数字之和，可用此性质写出整个杨辉三角。即第 $n$ 行的第 $i$ 个数等于第 $n−1$ 行的第 $i−1$ 个数和第 $i$ 个数之和，状态转移方程为：

$$dp[i][j] = dp[i-1][j-1] + dp[i-1][j]$$

🔧 代码实现

1、动态规划

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);
        for (int i = 0; i < numRows; ++i) {
            ret[i].resize(i + 1);
            ret[i][0] = ret[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
            }
        }
        return ret;
    }
};

📊 复杂度分析

1、动态规划

• 时间复杂度：$O(n^2)$，需要逐行计算。
• 空间复杂度：$O(1)$，不考虑返回值的空间占用。

🎯 总结

• 核心思想：经典的动态规划思路，要记住模板。