inohilogスマートフォン用の表示で見るinohilog/var/log/inohiroこの広告は、90日以上更新していないブログに表示しています。渡されて、一度に一歩もしくは二歩登れるときに、登るパターンの総数を計算する。解けた、一発で解けたんだけど、なんか変な解き方をしてしまって、いまいちスッキリしない。https://github.com/inohiro/LeetCode/blob/master/70_climbing_stairs/self.rbhttps://leetcode.com/problems/climbing-stairs/ナイーブにやると、一歩のときと二歩のときの全組み合わせを計算することになるので、なんだか(計算量が)まずそうだなと思った。変わったときに、組合せと結果がどう変わるかを書き出してみた。偶数のとき)と数えていけば良さそうだが、一歩と二歩が混ざるときはそう簡単に計算できないことがわかった。総段数のうちで、二歩で歩く割合を徐々に増やしたときのパターンを数え上げれば良さそうだった。ときの組合せ(lCm)の和が最終的な結果になることがわかった(このあと順列と組合せで混乱して、無駄に時間を使ってしまった)。ときの和になっているので、フィボナッチ数を数えるように動的計画法で解けるねって書いてあって、なるほどーという感想だった。たしかに動的計画法だ。次回はもっと早く気が付きたい...https://github.com/inohiro/LeetCode/blob/master/70_climbing_stairs/solution_dp.rb組合せの数の確認には、以下のサイトが便利だった。知ってたけど、単純に数を数えてくれるメソッドがあると便利そうだ。ListsArchiveはてなブログをはじめよう!InoHiroさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。