Quiz
https://yukicoder.me/problems/no/786
Submit
https://yukicoder.me/submissions/329556
解法
- dp[i] : i段登るときのパターン数とする
- dp[i]は、
- dp[i-2]から2段UP
- dp[i-1]から1段UP
- という遷移から来ることができるので、
- dp[i] = dp[i-2] + dp[i-1] となる
- 明らかなdp[1], dp[2], dp[3]は手動で埋めておく
感想
- 動的計画法の入門にすごくいい
- ナップサックよりも手頃