100日アルゴリズム[5日目・動的計画法(パスカルの三角形)]

解いた問題

https://leetcode.com/problems/pascals-triangle/

回答

function generate(numRows: number): number[][] {
    const dp:number[][] = []
    for (let i:number = 0; i < numRows; i++) {
        dp[i] = [];
        dp[i][0] = 1;
        dp[i][i] = 1;
    }

    for (let i:number = 2; i < numRows; i++) {
        for (let j:number = 1; j < i; j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        }
    }
    return dp;
};

パスカルの三角形は上から1段目と2段目の数は[1]と[1,1]かつ、どの段の一番左の数字と一番右の数字は1なので最初のfor文でその設定をします。

続いて、現在の行の列の数字は、前の行の1列前の数値と前の行の同じ列の数字を足したものになるので、その計算をfor文を使って2次元配列に書き込みます。