Pascal's Triangle

アルゴリズム概要

ステップバイステップ解説

numRows = 5 を例に、アルゴリズムの各ステップを追います。

Python 実装

▸ 業務開発版（型検証・コメント付き）

from __future__ import annotations


class Solution:
    """LeetCode 118: Pascal's Triangle — 行の積み上げ法"""

    def generate(self, numRows: int) -> list[list[int]]:
        # ── 入力検証（型チェック） ────────────────────────────────────
        # Python では bool が int のサブクラスなので先に bool を弾く
        if isinstance(numRows, bool) or not isinstance(numRows, int):
            raise TypeError(f"numRows must be int, got: {type(numRows).__name__}")

        # ── 入力検証（範囲チェック） ──────────────────────────────────
        if numRows < 1 or numRows > 30:
            raise ValueError(f"numRows must be 1‒30, got: {numRows}")

        # ── 結果格納用リスト ──────────────────────────────────────────
        triangle: list[list[int]] = []

        # ── 行を 1 行ずつ積み上げる ───────────────────────────────────
        for row_index in range(numRows):
            current_row = self._build_row(triangle, row_index)
            triangle.append(current_row)

        return triangle

    def _build_row(self, triangle: list[list[int]], row_index: int) -> list[int]:
        # 基底条件1：行0 は [1] 固定（前行が存在しないので早期リターン）
        if row_index == 0:
            return [1]

        # 基底条件2：行1 は [1, 1] 固定（内側の要素が存在しない）
        if row_index == 1:
            return [1, 1]

        # 行2以降：前の行を参照して内側の要素をリスト内包表記で計算
        prev: list[int] = triangle[row_index - 1]

        # CPython の LIST_APPEND 命令が効くため、for+append より高速
        inner: list[int] = [
            prev[col - 1] + prev[col]   # 真上の左 + 真上の右
            for col in range(1, row_index)
        ]

        return [1] + inner + [1]

入力: numRows = 5

[検証] isinstance(5, bool)→False, isinstance(5, int)→True, 1≤5≤30 ✅

[row_index=0] _build_row([], 0)  → [1]             triangle=[[1]]
[row_index=1] _build_row(.., 1)  → [1,1]            triangle=[[1],[1,1]]
[row_index=2] prev=[1,1]
              inner: col=1 → 1+1=2  →  inner=[2]
              return [1]+[2]+[1] = [1,2,1]            triangle=[[1],[1,1],[1,2,1]]
[row_index=3] prev=[1,2,1]
              inner: col=1→1+2=3, col=2→2+1=3  →  inner=[3,3]
              return [1,3,3,1]                        triangle=[..,[1,3,3,1]]
[row_index=4] prev=[1,3,3,1]
              inner: col=1→1+3=4, col=2→3+3=6, col=3→3+1=4  →  inner=[4,6,4]
              return [1,4,6,4,1]                      triangle=[..,[1,4,6,4,1]]

出力: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] ✅

▸ 競技プログラミング版（LeetCode 提出用・最短実装）

class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        tri: list[list[int]] = [[1]]
        for i in range(1, numRows):
            p = tri[-1]          # tri[-1] → 末尾行を O(1) で取得（Python の負インデックス）
            tri.append([1] + [p[j-1] + p[j] for j in range(1, i)] + [1])
        return tri

処理フローチャート

計算量分析

📖 用語集

このページで登場した専門用語をまとめました。分からない言葉が出てきたときに参照してください。（五十音順）