<style>
.font{
font-family:"DFKai-sb",Garamond, serif;
padding: 10px;
font-size : 115%;
line-height: 2;
}
.titles{
font-family:"DFKai-sb",Garamond, serif;
padding: 20px;
font-size : 150%;
line-height: 2;
}
.small_title{
font-family:"DFKai-sb",Garamond, serif;
padding: 15px;
font-size : 130%;
line-height: 2;
}
</style>
# DP 動態規劃

&nbsp;<font class = "font"> 動態規劃的基本想法簡單概括就是：**算過一遍的絕不算第二遍，以空間換取時間**。常常應用在**最佳化問題**上。</font>

&nbsp; <font class = "font">首先，DP 的核心問題是**列舉**，凡是可以用 DP 優化的問題，都可以暴搜，<b><font color=43BAF1>但是可以暴搜的卻不一定可以用 DP 解決</font></b>。這是因為 DP 問題很多都存在 **重疊子問題**，舉個例子：</font>
### <font class = "font">經典範例：費氏數列</font>
<font class = "font">這範例基本上用到爛了，基本上所有教學都舉了這個例子。其中最重要的原因是這個例子最能簡單暴力的彰顯 DP 的威力。費氏數列定義如下：</font>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

<font class = "font">我們可以根據定義寫出簡單的遞迴：</font>

int f(int n){
    if (n==0) return 0;
    if (n==1 || n==2) return 1;
    return f(n-1)+f(n-2);
}

<font class = "font">這個寫法的時間複雜度是 $O(2^n)$，明顯太大。</font>

<font class = "font">但這裡我們注意到費氏數列的遞迴其實不斷地拿之前算過的數值來計算，這就是一種**重疊子問題**，而我們可以用**備忘錄**來減去不必要的計算：</font>

int fib(int n) {
        if (n==0) return 0;
        if (n==1) return 1;
        vector<int> table(n+1);
        table[0]=0;
        table[1]=1;
        table[2]=1;
        for(int i=3;i<=n;i++){
            table[i]=table[i-1]+table[i-2];
        }
        return table[n];
    }

<font class = "font">其中的 $table$ 就是備忘錄，記錄算過的數值，之後要用的時候查表即可，成功將時間複雜度降到 $O(n)$。</font>

## <font class = "font">題目練習</font>

#### <font class = "small_title">1.Coin Change</font>
&nbsp;&nbsp;&nbsp;&nbsp; <font class = "font">經典的湊零錢問題</font>

<font class = "small_title">筆記區：</font>
>https://hackmd.io/@rickrool/SyP7ZN1Ai

---

#### <font class = "small_title">2.Unique Binary Search Trees</font>

&nbsp;&nbsp;&nbsp;&nbsp; <font class = "font">第一次真的看不出是 DP 問題，直到我查到了 **卡塔蘭數列** 才知道解法。</font>

<font class = "small_title">筆記區：</font>
>https://hackmd.io/@rickrool/Sy0Lg5-Q3

---

#### <font class = "small_title">3.連續元素的和</font>

&nbsp;&nbsp;&nbsp;&nbsp; <font class = "font">一樣是經典 DP 題</font>
* <font class = "font">特別要注意的是這題是 「子序列問題」，要連續。下面會有「子陣列」問題，不需要連續。</font>

<font class = "small_title">筆記區：</font>
>https://hackmd.io/@rickrool/BkdZUppbn

---

#### <font class = "small_title">4.城市道路連通網</font>

&nbsp;&nbsp;&nbsp;&nbsp; <font class = "font">其實題目直覺上我會用圖論解，但查過後才知道可以用 DP 。</font>

<font class = "small_title">筆記區：</font>
>https://hackmd.io/@rickrool/SJj70QCf2

---

#### <font class = "small_title">5.Longest Increasing Subsequence</font>

&nbsp;&nbsp;&nbsp;&nbsp; <font class = "font">這題是「子陣列問題」，相對於子序列問題更加麻煩。</font>

<font class = "small_title">筆記區：</font>
>https://hackmd.io/@rickrool/SkzQpZWHh

---

#### <font class = "small_title">6.Longest Common Subsequence</font>

&nbsp;&nbsp;&nbsp;&nbsp; <font class = "font">經典的 LCS 問題</font>

<font class = "small_title">筆記區：</font>
>https://hackmd.io/@rickrool/HyXa1i1I2

---

#### <font class = "small_title">7. Divisibility</font>

&nbsp;&nbsp;&nbsp;&nbsp; <font class = "font">這題需要轉個彎，先從除法基本概念下手，即可慢慢推得狀態轉移方程。</font>

<font class = "small_title">筆記區：</font>
>https://hackmd.io/@rickrool/ryYhuUMH2