perogram

No.786 京都大学の過去問

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]は手動で埋めておく

感想

  • 動的計画法の入門にすごくいい
  • ナップサックよりも手頃