おーじのゆるゆる精進日記 #5

再帰のいい練習問題です.

レベル0バーガーはパティ1枚.

レベルLバーガーは(パン1枚)+(レベルL-1バーガー)+(パティ)+(レベルL-1バーガー)+(パン1枚)で構成される.

下からX層の中で何枚のパティがありますか？

レベルLバーガーの内容はレベルL-1バーガーがわかればわかります.

よって再帰関数f(n,x)をレベルnバーガーの下からx層に含まれるパティの枚数として定義します.

ここからは公式の解説と同じような解法になりますのでこちらで(https://img.atcoder.jp/abc115/editorial.pdf)許してください><

この問題はなかなか言語化するのが難しいです.

とにかくレベルLバーガーに関して下から再帰で実装をしていきます.

そのままだとTLEするためレベルL-1の層の厚さやレベルL-1のパティの枚数を前計算してあげればokです.

再帰大事！！！