Introduction

對於學過 DP 的人來說，這題應該是不陌生吧。
許多教科書都會告訴你 DP 需要滿足重疊子問題和最佳子結構，但現在，我們現把它放一邊。

有人認為 DP 就是有存答案的 DFS，嗯...很棒，然後呢？你 DFS 夠熟就能解決 DP 題嗎？
事實上，相比於 DFS，DP 有更多獨特之處。

調用情形密集

狀態時常被其他狀態使用，才需要存每個狀態的答案。

狀態複雜度不高

老實說，一個 DP 用到四個狀態(狀壓算一個)已經非常少見，更別提五六個了。
另外，狀態常是 0/1 或連續區間(1,2,3...)，
而離散的(1,2,3,5,8...)比較少，這時就要用 map 存答案了。

狀態能完美地表現目標狀況

舉上面題目例子，dp[i] 一定表示所有走 i 階的情況，不能有遺漏。

困難題狀態都很邪門

AtCoder Beginner Contest 220H
看完記得洗洗眼睛。

回傳值簡單

dp[i] 常表示一個值，表示兩個值(pair)的幾乎沒看過，三個值以上...你乾脆跟我說 APCS 第一題需要線段樹好了。

對了，在 DP 的世界中，任何東西都能當成狀態，只要狀態設計完善，轉移式良好，不需消耗太多時間和記憶體，就是好的解法。
明天才會開始講題目，有時間可以先寫寫看這些經典題。