※こちらの記事は Pascal's Triangle IIをした際にAIに聞いてみた学習メモです

[leetCode] 119. Pascal's Triangle II

solutionで見たこのコード

var getRow = function(r) {
   let ans = new Array(r + 1)
   ans[0] = ans[r] = 1;
   for(let i = 1, up = r; i < r; i++, up--){
    ans[i] = ans[i-1] * up/i // ここ
   }
   return ans
};

ここが何しているのかわからない。なぜその方法で現在の値が求められるのか

先ずこのコードがやっていることから

このコードは、パスカルの三角形の指定された行を計算するものです。プログラミングやコンピューターサイエンスの知識がなくてもわかりやすく説明しますね。

パスカルの三角形とは？
パスカルの三角形は、1 から始まる数の三角形で、各行の両端は必ず 1 です。真ん中の数は、ちょうど上の行の左右の数字を足したものになります。

例：
コードをコピーする
    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1
各行の最初と最後は 1 で、その間の数は上の行の2つの数を足したものです。

このコードがやっていること
初期化:

入力として指定された行 r に基づいて、長さ r + 1 の配列 ans を作ります。これは、パスカルの三角形の r 番目の行の数字を保持するためです。
最初の数字 (ans[0]) と最後の数字 (ans[r]) を 1 に設定します。これは、どの行でも最初と最後が常に 1 であるためです。
真ん中の数を計算:

1 から r-1 までの位置に対して、順番に数を計算します。
ans[i] を計算するとき、前の数字 (ans[i-1]) に上の行の値 (up) を掛け、位置 i で割ることで、現在の位置の値を求めます。
up は毎回 1 ずつ減らしていきます。これは、パスカルの三角形の法則に従っているためです。
結果を返す:

結果を返す:

最終的に ans 配列にはパスカルの三角形の r 番目の行が格納されているので、それを返します。
例で説明
たとえば、r = 4 の場合、このコードは次のように動作します：

ans は [1, , , , 1] で始まります。
// ここ
位置 i = 1 のとき、ans[1] = 1 * 4/1 = 4。
位置 i = 2 のとき、ans[2] = 4 * 3/2 = 6。
位置 i = 3 のとき、ans[3] = 6 * 2/3 = 4。
最終的な ans は [1, 4, 6, 4, 1] となり、これはパスカルの三角形の5行目に対応します。

この方法で、パスカルの三角形の特定の行を簡単に計算できます。

ここを詳しく聞く

ans[i] を計算するとき、前の数字 (ans[i-1]) に上の行の値 (up) を掛け、位置 i で割ることで、現在の位置の値を求めます。

この計算方法は、パスカルの三角形の組み合わせの性質を利用しているからです。

この式は、組み合わせの性質に基づいています。r 行の k 番目の値は、r 行の k-1 番目の値を使って求められるのです。

具体的に、この式が成り立つ理由は次の通りです：

分子の (r - (k-1)) は、残りの選択肢の数を表します。つまり、r 個の要素の中から k 個を選ぶ際に、新しい要素を追加する可能性の数です。
分母の k は、新しく選んだ要素の位置を正規化するために使います。
したがって、ans[i] を計算する際に ans[i-1] * (up/i) を用いると、次の組み合わせの値が効率的に得られるのです。

この方法によって、パスカルの三角形の各行の値を前から順番に計算できるため、無駄な計算を避けることができます。

いやー、厳しいな...
ちょっと効率悪くても他のアルゴリズムで解いて説明できた方がいいな
..
と感じました

結局これが一番わかりやすい。時間複雑度はO(rowIndex ^ 2)ですけれど

var getRow = function(rowIndex) {
    let triangle = [];

    for (let i = 0; i <= rowIndex; i++) {
        let row = [];
        for (let j = 0; j <= i; j++) {
            if (j === 0 || j === i) {
                row.push(1); // The first and last elements in each row are 1
            } else {
                let prevRow = i - 1;
                let leftVal = triangle[prevRow][j - 1];
                let rightVal = triangle[prevRow][j];
                row.push(leftVal + rightVal); // Sum of the two numbers above.
            }
        }
        triangle.push(row);
    }

    return triangle[rowIndex];
};

私はコードに残すなら最後の方にします

• 説明ができる
• この問題ではその時間複雑度はやむなし
• もしパフォーマンスが重要視される場合はそっちを見てねというコメントとリンクを残す
  ぐらいがいいと思う