解いた問題

leetcode 119. Pascal's Triangle II
パスカルの三角形において、引数で指定された段の結果だけを返してねって問題。

最初の解法

進研ゼミでやったやつだ！！
https://zenn.dev/zenn_mita/articles/82cc5f2cad5952

ということで意気揚々と問題に取り組む。

first.py

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        triangle = []
        for i in range(rowIndex+1):
            i_row = [1] * (i + 1)
            for j in range(1, i):
                i_row[j] = triangle[i-1][j-1] + triangle[i-1][j]
            triangle.append(i_row)
        
        return triangle[rowIndex]

当然一発正解。

イヤ簡単っすわ～～
アルゴリズム極めるのもそう遠くないっすわ～～～～

と天狗になったのですが、ふと同じ系統の問題を繰り返し出題することあるのか？と思い答えを確認。
30秒足らずで伸びたハナをへし折られました。

答え

answer_1.py

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        row = [1]
        for _ in range(rowIndex):
            # 次の行を作るときだけ一時的に0を足す
            padded = [0] + row + [0]
            new_row = []
            for i in range(len(padded) - 1):
                new_row.append(padded[i] + padded[i+1])
            row = new_row
        return row

これが最適解①。
やっていることは近いが求められている段の計算のみ行っているため、空間計算量≒メモリ使用量が$O(k)$で済む。

僕の解法は全部広げるので$O(k^2)$なのでめちゃくちゃ効率悪いです。
ちなみにkはrowIndexのサイズ。

メモリ使用量を全く考えていなかったということもへこんだが、答えをパッと見ても何しているのかわからなかったことに一番へこんだ。

しかも最適解がもう一つあって、こっちのほうがleetcodeらしいコードっぽい。

answer_2.py

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        row = [0] * (rowIndex + 1)
        row[0] = 1
        for i in range(1, rowIndex + 1):
            # 後ろから更新するのがポイント
            for j in range(i, 0, -1):
                row[j] += row[j - 1]
        return row

これが最適解②

...うーんわからん。
なのでちょっと調べました。

調べた結果

最適解①がやっているのはCNNの畳み込みみたいなことだと気づいた。
端を0でパディングして隣り合っている数字を畳み込んだものが次の層の出力になっている。

わかれば納得だがなぜこんなことを思いつくのかわからなかったので調べた。

流れ的には隣り合わせて計算したら次の層が計算できそうだとなるが、そうなると端がifを使って分岐しないといけなくなる
しかしそれだと気持ち悪いから何とかして同様の処理で片づけられないかを考えた。
その時計算できない理由がout of rangeだからなので、計算結果に影響が出ないように周りに0を付けた、という感じ。

上記納得はできたが思い付きはしないな...という感想。

最適解②は同様の発想ではあるがよりメモリ効率を上げるために1つのリスト内ですべての処理を終えるもの。
逆から計算しているのもその一環ではあるが、前からやろうと思えばできるのでは？と思った...がたぶんできないんだろうなと感じている。

難しそうだし実際僕レベルが使うかと言われたら微妙なので、一旦保留でいいかという結論に。

感想

ダニング=クルーガー効果でいう「バカの山」から突き落とされました。

精進します。