---
title: 基礎DP
tags: DP
robots: noindex, nofollow
langs: zh
---

# DP介紹
DP = 遞迴+記錄下曾經算過的部分
把問題轉化成遞迴問題，用陣列儲存的方式優化速度！
TopDown: 認真做遞迴，認真把傳進去的參數當作陣列的位置存放
BottomUp: 用迴圈去填完表，再查詢 (**建議**)

## 轉移
狀態: 問題本身所存在的一些性質，多數為未知的，僅有初始值是
從已知的狀態去推導未知的狀態

:warning:**初始狀態很重要**

## DP秘技的拉
1. 設定狀態
設定陣列的維度與陣列內容所表達的意義
2. 設定轉移狀態
制定如何用已知的解得出未知問題的答案
3. 制定合理的初始狀態
將足夠且合理的初始狀態預先填入陣列中
john的話DP問題就可以有條理的解決掉了 :smile:

## 例題1
### 題目敘述
:::info
爬$n$層樓梯, 每次能往上爬$1$或$2$或$3$層, 問你爬樓梯的方法數?
:::

1. 設定狀態

- $dp(n)$ 表示爬到第 $n$ 層樓梯的方法數
2. 設定轉移狀態

- 想一想之後發現，第 $n$ 層的樓梯可以從第 $n-1$ 或第 $n-2$ 或第 $n-3$ 層樓梯爬到, 所以 $dp(n) = dp(n-1)+dp(n-2)+dp(n-3)$
3. 制定合理的初始狀態

- $dp(1)$ 和 $dp(2)$ 和 $dp(3)$ 似乎不能用以前算過的答案來推知, 似乎就是初始狀態了, 所以先自己設定好初始狀態的值, $dp(1)=1,\;dp(2)=2,\;dp(3)=\{(1,1,1), (1, 2), (2, 1), (3)\}=4$

4. 所以應該可以寫成這樣

int dp[100000];
dp[1] = 1, dp[2] = 2, dp[3] = 4;
for (int i = 4; i <= n; i++) {
    //這邊注意大括號不要換行, 不然你會變得跟某位重雨學長一樣電
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}

## 優質atcoder edu **dp** contest
### 練啦哪次不練
- https://atcoder.jp/contests/dp/tasks