118. 杨辉三角

Bin大约 2 分钟

118. 杨辉三角

📝 题目描述

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

在杨辉三角中，每个数是它左上方与右上方两个数的和：

1 1 1 1 2 1


1 3 3 1
1 4 6 4 1

📌 示例

示例 1

输入：


numRows = 5

输出：


[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

示例 2

输入：


numRows = 1

输出：


[[1]]

🚀 最优解：动态规划（按行生成）

🔍 思路解析

杨辉三角的生成规则：

每一行的首尾都是 1
中间的元素由上一行的两个数字相加：


cur[j] = pre[j-1] + pre[j]

例如生成第 4 行（1,3,3,1）：

第一个数字 1
中间：
- 3 = 1 + 2
- 3 = 2 + 1
最后一个数字 1

每一行都依赖上一行，因此我们可以从上往下依次生成。

✅ 完整代码（Java）

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取行数
        int numRows = scanner.nextInt();

        Solution solution = new Solution();
        List<List<Integer>> result = solution.generate(numRows);

        // 输出结果
        for (List<Integer> row : result) {
            for (int i = 0; i < row.size(); i++) {
                System.out.print(row.get(i));
                if (i < row.size() - 1) {
                    System.out.print(" ");
                }
            }
            System.out.println();
        }

        scanner.close();
    }
}

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        if (numRows == 0) return ans;

        // 第一行固定为 [1]
        List<Integer> firstRow = new ArrayList<>();
        firstRow.add(1);
        ans.add(firstRow);

        for (int i = 1; i < numRows; i++) {
            List<Integer> preRow = ans.get(i - 1);
            List<Integer> curRow = new ArrayList<>();

            curRow.add(1); // 每行开头的 1

            for (int j = 1; j < i; j++) {
                int sum = preRow.get(j - 1) + preRow.get(j);
                curRow.add(sum);
            }

            curRow.add(1); // 每行结尾的 1

            ans.add(curRow);
        }

        return ans;
    }
}