---
tags: 教材
---

# 動態規劃

---

## 基本觀念

1. 定義子問題。
2. 找出問題與子問題之間的遞迴的方式進行計算。
3. 找出子問題的計算順序來避免以遞迴的方式進行計算。

---

## 範例(費式數列)

----

### 遞迴
如果依照遞迴的想法，可快速寫出下列程式:

#include<iostream>
using namespace std;

long long fib(int n){
    if(n<3)return 1;
    return fib(n-1)+fib(n-2);
}

int main(){
    int n;
    cin>>n;
    cout<<fib(n)<<'\n';
    return 0;
}

----

但是我們真的需要這麼多的運算嗎?

digraph FIB{
    nodesep=0.1

    "fib(5)"->{"fib(3) " "fib(4)"}
        "fib(3) "->{"fib(1)" "fib(2)"}
            "fib(4)"->{"fib(2) " " fib(3) "}
            " fib(3) "->{" fib(1) " " fib(2) "}
            
}

----

### Top-down memoization

#include<iostream>
using namespace std;
long long dp[100005];
long long fib(int n){
    if(dp[n]!=-1)return dp[n];
    return dp[n]=fib(n-1)+fib(n-2);
}

int main(){
    for(int i=0;i<100005;++i)dp[i]=-1;
    dp[1]=1,dp[2]=1;
    int n;
    cin>>n;
    cout<<fib(n)<<'\n';
    return 0;
}

----

### Bottom-up

#include<iostream>
using namespace std;
long long fib[100005];

int main(){
    fib[1]=1,fib[2]=1;
    int n;
    cin>>n;
    for(int i=3;i<=n;++i)
        fib[i]=fib[i-1]+fib[i-2];
    cout<<fib[n]<<'\n';
    return 0;
}

---

## 習題1

----

### 題目連結
[Frog1](https://atcoder.jp/contests/dp/tasks/dp_a)
* 給定N個石頭，第i個石頭高度為$h_i$
* 第i個石頭只能跳到第i+1或第i+2個石頭
* 彈跳的費用為$|h_i-h_j|$，j為目的地
* 求到第n個石頭的花費最小值?
* $2\le N \le 10^5$

----

### 思路

* $dp[i]$為走到第i格時最小的花費。
* $dp[i]=min(dp[i-1]+距離,dp[i-2]+距離)$

---

## 習題2

----

### 題目連結
[Frog2](https://atcoder.jp/contests/dp/tasks/dp_b)
* 給定N個石頭，第i個石頭高度為$h_i$
* 給定最遠距離K
* 第i個石頭能跳到第i+1,i+2....,i+K個石頭
* 彈跳有費用為$|h_i,h_j|$，j為目的地
* 求到第n個石頭的花費最小值?
* $2\le N \le 10^5$，$1\le K \le100$

----

### 思路

* $dp[i]$為走到第i格時最小的花費。
* $dp[i]$能由dp[i-1]....dp[i-k]組成，要考慮前面所有狀態值找到最小值
* $dp[i]=min(dp[j]+abs(fg[i]-fg[j]),dp[i])$
* $i-k\le j\le i-1$

---

## 習題3

----

### 題目連結
[最小監控鄰居的成本]
* 給定N個區塊，第i區塊監測花費為$c_i$
* 監控第i塊區間時，i-1和i+1塊區間也都會被監控
* 求所有區塊都能監視到的最小成本
* $N \le 10^5$

----

### 思路

* 這題看似和前面類似但dp[i-1]的值可能來自沒有挑選到i-1的值
* 定義$dp[i]$為必選i
* $if$ $i>2$
* $dp[i] = c[i] + min(dp[i-1], dp[i-2], dp[i-3])$

---

## 習題4

----

### 題目連結
[LCS]

* 給定兩字串s1,s2
* 求其最長相同子字串

----

### 思路

* 我們定義dp[i][j]為s1的前i個字元和s2的前j個字元中，最長的lcs。
* $if$ $s1[i]==s2[j]$
* $dp[i][j]=dp[i-1][j-1]+1$
* $if$ $s1[i]!=s2[j]$
* $dp[i][j]=max(dp[i-1][j],dp[i][j-1])$
* 至於兩個都不選的情況無需特別判斷，因為其狀態是包含在只刪一個的狀態中。

----

### 挑戰題

[洛谷1439](https://www.luogu.com.cn/problem/P1439)

---

## 習題5

----

### 題目連結
[LIS]

* 給定N個數，求數列中最常遞增子數列長度

----

### 思路

* dp[i]為第i點結束最常LIS長度
* $j<i \; and \; s[j]<s[i]$
* $dp[i]=max(dp[j]+1)$

----

### 優化

* 原複雜度$O(n^2)$ -> $O(nlogn)$
* 數字較小結尾，lis數列越長
* ex: 1 3 4 -> 1 2 4
* lis數列具單調性，所以二分搜!!!

----

### 挑戰題

[洛谷P1091](https://www.luogu.com.cn/problem/P1091)

---

## 習題6

----

### 題目連結
[背包問題](https://atcoder.jp/contests/dp/tasks/dp_d)

* 給定N個物品，第i個物品重量為$W_i$，價值$V_i$
* 背包容量為W
* 求物品重量和不超過W，價值總和之最大值?
* $1\le n \le 100$ , $1\le W \le 10^5$

----

### 思路

* dp[i][j]=只考慮前i個物品，背包容量為j的最大價值總和
* 考慮第i樣物品
* 選: $dp[i][j]=dp[i-1][j-W_i]+V_i$
* 不選: $dp[i][j]=dp[i-1][j]$

----

### 挑戰題

[knapsack2](https://atcoder.jp/contests/dp/tasks/dp_e)

---

## 習題7

----

### 題目連結
[背包問題](https://atcoder.jp/contests/dp/tasks/dp_d)

* 給定N個物品，第i個物品重量為$W_i$，價值$V_i$
* 背包容量為W
* 每樣物品無限制選取數量
* 求物品重量和不超過W，價值總和之最大值?
* $1\le n \le 100$ , $1\le W \le 10^5$

----

### 思路

* dp[i][j]=只考慮前i個物品，背包容量為j的最大價值總和
* 考慮第i樣物品
* 選: $dp[i][j]=dp[i-1][j-W_i]+V_i$
* 不選: $dp[i][j]=dp[i-1][j]$

----

### 挑戰題

[knapsack2](https://atcoder.jp/contests/dp/tasks/dp_e)

---