LeetCode 118. 杨辉三角

Categories:

题目描述
思路分析
1. 解法一：动态规划构造（推荐）
相似题目

题目描述

✅ 118. 杨辉三角

思路分析

解法一：动态规划构造（推荐）

核心思路：

第 i 行有 i+1 个元素，两端为 1。

中间元素由上一行相邻元素相加得到。

按行逐步构造即可。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示行数。

空间复杂度：O(n^2)，用于存储结果。

import java.util.*;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            row.add(1);

            // 计算中间元素
            for (int j = 1; j < i; j++) {
                int val = res.get(i - 1).get(j - 1) + res.get(i - 1).get(j);
                row.add(val);
            }

            if (i > 0) {
                row.add(1);
            }

            res.add(row);
        }

        return res;
    }
}

func generate(numRows int) [][]int {
	res := make([][]int, 0, numRows)

	for i := 0; i < numRows; i++ {
		row := make([]int, 0, i+1)
		row = append(row, 1)

		// 计算中间元素
		for j := 1; j < i; j++ {
			row = append(row, res[i-1][j-1]+res[i-1][j])
		}

		if i > 0 {
			row = append(row, 1)
		}

		res = append(res, row)
	}

	return res
}

相似题目

题目	难度	考察点
119. 杨辉三角 II	简单	动态规划
120. 三角形最小路径和	中等	动态规划
62. 不同路径	中等	动态规划
63. 不同路径 II	中等	动态规划
64. 最小路径和	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/01053064