C++で解くパスカルの三角形 II：k行目を効率的に求めるアルゴリズム

パスカルの三角形 II とは

0 以上のインデックス k（k ≤ 33）が与えられたとき、パスカルの三角形の k 行目を求める問題を考えてみましょう。

例えば、入力が 3 の場合、出力は [1, 3, 3, 1] となります。

パスカルの三角形とは、各行の両端が 1 であり、それ以外の要素が直上の行の左右隣接する2つの値の和になるという性質を持つ三角形です。この問題では、空間計算量 O(k) だけを使って、指定された行のみを効率的に生成することが求められます。

解法のアプローチ

この問題は「1次元配列をその場で更新する（in-place更新）」テクニックを使うことで、追加の配列を用意せずに解くことができます。手順は以下の通りです。

• サイズが rowIndex + 1 の配列 pascal を定義し、すべて 0 で初期化します。
• r = 0 から rowIndex まで、以下を繰り返します。
  • pascal[r] := 1 とし、prev := 1 を設定します。
  • i = 1 から r - 1 まで、以下を繰り返します。
    • cur := pascal[i] として現在の値を退避させます。
    • pascal[i] := pascal[i] + prev と更新します。
    • prev := cur として退避した値を引き継ぎます。
• 最後に pascal を返します。

ポイントは、配列を左から右へ走査しながら更新する際に、更新前の値を一時変数 prev / cur で保持しておくことです。これにより、前の行の情報を失うことなく、1つの配列だけで行を順次構築できます。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> getRow(int rowIndex) {
      vector<int> pascal(rowIndex + 1, 0);
      int prev, cur, r, i;
      for (r = 0; r <= rowIndex; r++) {
         pascal[r] = prev = 1;
         for (i = 1; i < r; i++) {
            cur = pascal[i];
            pascal[i] += prev;
            prev = cur;
         }
      }
      return pascal;
   }
};
main(){
   Solution ob;
   print_vector(ob.getRow(3));
}

入力

3

出力

[1, 3, 3, 1]

計算量について

このアルゴリズムの時間計算量は O(k²) です。外側のループが k 回、内側のループが最大で k 回回るためです。一方、空間計算量は出力用の配列を除けば O(1)、つまり追加の領域をほとんど必要としないのが大きな特徴です。二項係数を直接計算する方法もありますが、オーバーフローや割り算の扱いに注意が必要なため、このような漸化式による構築方法は安全で分かりやすいアプローチと言えます。