70. Climbing Stairs
登る階段のステップ数 n が渡されて、一度に一歩もしくは二歩登れるときに、登るパターンの総数を計算する。解けた、一発で解けたんだけど、なんか変な解き方をしてしまって、いまいちスッキリしない。
- https://github.com/inohiro/LeetCode/blob/master/70_climbing_stairs/self.rb
- https://leetcode.com/problems/climbing-stairs/
ナイーブにやると、一歩のときと二歩のときの全組み合わせを計算することになるので、なんだか（計算量が）まずそうだなと思った。とりあえずコードを書き始める前に、よく考えて方針を決めてから取り掛かる習慣をつけたいので、与えられるステップ数 n が変わったときに、組合せと結果がどう変わるかを書き出してみた。
すべてを一歩で登りきるとき、すべてを二歩で登りきるとき（ただし段数 n が偶数のとき）と数えていけば良さそうだが、一歩と二歩が混ざるときはそう簡単に計算できないことがわかった。総段数のうちで、二歩で歩く割合を徐々に増やしたときのパターンを数え上げれば良さそうだった。
書き出した組合せを見ると、それぞれのステップで、n 段数を登る試行 l のうち、二歩で登る回数が m のときの組合せ（lCm）の和が最終的な結果になることがわかった（このあと順列と組合せで混乱して、無駄に時間を使ってしまった)。一度配列を読むだけで良いので、計算量は O(n) 。
一方で、解説を読むと、あるステップ k のときの総パターン数はステップ k-1 と k-2 のときの和になっているので、フィボナッチ数を数えるように動的計画法で解けるねって書いてあって、なるほどーという感想だった。段数 1 のとき、2 のときがそれぞれわかってて、その先は (n-1) + (n-2) で数えていく。たしかに動的計画法だ。次回はもっと早く気が付きたい...
組合せの数の確認には、以下のサイトが便利だった。Ruby の Array#{combination, permutation} は知ってたけど、単純に数を数えてくれるメソッドがあると便利そうだ。
