116,117

DPの練習として良い問題の一つだと思った。俺はDPが苦手なので、色々考えた結果方法を思いついた訳だけど、どうやってこの考えに至ったのかが説明できない。悔しいなー。とりあえず考え方は続きに。ちなみに、DPはDouble Playじゃないよ！Double Playは全然苦手じゃないよむしろ最近絶好ｔｒｙ

長さ0の配置方法は1通り。長さがN以下のときの配置方法が何通りか分かっているとする。また、配置仕方はtable[n]通りと表現するする。このとき、N+1に長さがlの板の右端が来るように置くとすると、table[N+1-l]通りの配置方法があると言える。lは1〜4の4種類あるので、table[N] = table[N - 1] + table[N - 2] + table[N - 3] + table[N - 4]となる。

こんな感じ。最初はメモ探をしてみようとか思ってた。でもそうなると、どの状態で1通り並べたと言えるのかがわからなく、結局左から始めてボトムアップに計算していく方法に落ち着いてしまった。こういう問題を考えるといつもひらめきが先行してしまって、論理的に理想解に辿り着くことが出来ない。なので、似たような問題が出てきてもまたひらめきに頼ることになってしまう。どうすれば良いんだろう…。