Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Easy 118. Pascal's Triangle

leetcode
tags: leetcode

問題

非負整数numRowsが与えられた時, パスカルの三角形(Pascal's triangle)の最初のnumRows段を生成せよ

解法1(recursive)

まずパスカルの三角形ってなんだよって思いますよね

パスカルの三角形

下の図のような数列を三角形状に並べたもののことです1

上から$n - 1$段目, 左から$k - 1$番目の数が二項係数$\begin{pmatrix} n - 1 \cr k - 1 \end{pmatrix}$になっています

二項係数の再帰的性質

この三角形は二項係数の再帰的な性質を利用しています

$\begin{pmatrix} n \cr k \end{pmatrix}$は$n$個のものから$k$個のものを選ぶ時の組み合わせです

これは$n$個からあるものを必ず選ぶ時と必ず選ばない時に分けて考えられます

必ず選ぶ時は残りの$n - 1$から$k - 1$個を選び, 必ず選ばない時は残りの$n - 1$個から$k$個を選ぶ必要があります

よって$\begin{pmatrix} n \cr k \end{pmatrix} = \begin{pmatrix} n - 1 \cr k - 1 \end{pmatrix} + \begin{pmatrix} n - 1 \cr k \end{pmatrix}$と書けます(ただし, $n \geq k, n \in \mathbb{N}$)

また,$\begin{pmatrix} n \cr n \end{pmatrix} = 1$, $\begin{pmatrix} n \cr 0 \end{pmatrix} = 1$です(それぞれ$n$個の集まりから$0$個を選ぶ方法, 全ての要素($n$個の要素)を選ぶ方法は1通りであるということに対応しています)

これが基底ですね

再帰的に解く

この問題ではこの性質を利用します

  • 最初に基底として最初の段を生成します
    • これは解決した問題です
  • 解決した問題を利用して次の段を生成します
  • この処理を行っている段の数がnumRowsになるまで繰り返します
  • 例外としてnumRowsが$0$のときは空の配列を返します
  • 入力を$n$とします
    • 時間計算量は再帰関数を$n$回実行し, その中で長さ$n$の配列を用意するので$O(n^{2})$
    • 空間計算量は再帰関数を$n$回実行し, 再帰関数ごとに$n$回の繰り返し処理をするので$O(n^{2})$

Python

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
      def helper(pascal, curRow, numRows):
        if curRow >= numRows:
          return
        row = [1]
        for col in range(1, curRow):
          row.append(pascal[curRow-1][col] + pascal[curRow-1][col-1])
        row.append(1)
        pascal.append(row)
        helper(pascal, curRow+1, numRows)
        
      if numRows == 0:
        return []
      else:
        pascal = [[1]]
        helper(pascal, 1, numRows)
        return pascal

C++

class Solution {
public:
  vector<vector<int>> generate(int numRows) {
    if (numRows == 0) {
      return {};
    } else {
      vector<vector<int>> pascal{{1}};
      helper(pascal, 1, numRows);
      return pascal;
    }  
  }

private:
  void helper(vector<vector<int>>& pascal, int curRow, int numRows) {
    if (curRow >= numRows) {
      return;
    }
    vector<int> row{1};
    for (int col = 1; col < curRow; col++) {
      row.push_back(pascal[curRow-1][col-1] + pascal[curRow-1][col]);
    }
    row.push_back(1);
    pascal.push_back(row);
    helper(pascal, curRow+1, numRows);
  }
};

解法2(iterative)

iterativeに解いてもrecursiveに解く際の再帰処理がfor文になるだけなので空間計算量と時間計算量は変わりません

Python

appendはあまり早いメソッドではないのですがPython力がないのでこんな感じに...

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
      if numRows == 0:
        return []
      elif numRows == 1:
        return [[1]]
      else:
        pascal = [[1]]
        for row in range(1, numRows):
          p_row = [1]
          for col in range(1, row):
            p_row.append(pascal[row-1][col] + pascal[row-1][col-1])
          p_row.append(1)
          pascal.append(p_row)
        return pascal

C++

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        if (numRows == 0) {
          return vector<vector<int>> {};
        } else {
          vector<vector<int>> ans{{1}};
          for (int i = 1; i < numRows; i++) {
            vector<int> row{1};
            for (int j = 1; j < i; j++) {
              row.push_back(ans[i-1][j-1]+ans[i-1][j]);
            }
              row.push_back(1);
              ans.push_back(row);
          }
          return ans;
        }
    }
};

まとめ

この問題は計算量がどちらの書き方でも変わらず, iterativeに書いた方がすっきり書けるのでiterativeに書いた方が良いでしょう

  1. wiki参照↩