Coding Prep 演算法資料結構教學

動態規劃 (dynamic programming)

動態規劃 (dynamic programming)

動態規劃 (Dynamic programming, DP) 不算是一種演算法，而是一種解決問題的方法。動態規劃的大概念就是把大問題分成很多個子問題，每次我們會把子問題的答案儲存起來，再利用子問題的答案來推算出大問題的答案。

可以用動態規劃解的題目都要滿足最佳子結構的性質，也就是局部的最佳解能決定全域最佳解，要不然分成子問題解的方法就不能使用了。

動態規劃有兩個最核心的概念: 狀態跟轉移。

狀態

狀態就是我們要怎麼儲存答案。我們需要先很清楚的定義好我們要用 DP 儲存甚麼的答案。這個階段非常重要，要有一個好的狀態才能夠比較好的轉移。

轉移

轉移就是我們要怎麼在不同狀態之間轉移答案，也就是，我們要怎麼從小問題的答案類推到大問題上面，也是一個遞迴關係式。

初始條件

初始條件就是一開始我們已知的答案，可以從這個當作基準點進行轉移。

這樣講可能會有點抽象，總之動態規劃就是要用已經算過，儲存好的比較小的問題的答案推出大問題的答案，就這樣從最小的初始條件慢慢推到大問題。講了一個實際了例子我相信這個概念就會清楚很多了 !

我們來看看老朋友費氏數列，也就是 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 的那個數列。我們就用動態規劃的概念來看看這題。

我們先從狀態開始，這題的狀態比較直觀，我們可以用 dp[i] = 費氏數列的第 i 項是甚麼。
接著是轉移，其實這題的轉移式子都已經給好了 dp[n] = dp[n-1] + dp[n-2]
最後就是初始條件，這題也已經給你了 dp[0] = 0, dp[1] = 1

現在我們就可以開始寫扣了 ! DP主要有兩種寫法 top-down 跟 bottom-up。

Top-down

就照著遞迴式子的方法從上往下跑，也就是從大問題直接遞迴下去小問題。通常會比較直觀。跟一般遞迴不一樣的是，我們需要紀錄每個狀態的答案，這樣如果重新跑到就不用再算一次了，會節省很多時間。

#include <bits/stdc++.h>
using namespace std;
int dp[100005];
int f(int i){
    if(i == 0) return 0;
    else if(i == 1) return 1;
    else if(dp[i]) return dp[i]; // 以經算過了
    else {
         dp[i] = f(i-1) + f(i-2);
         return dp[i];
    }
} 
int main(){
    int n;
    cin >> n;
    cout << f(n) << '\n';
}

Bottom-up

Bottom-up 就是從小問題用迴圈往上轉移到大問題。

#include <bits/stdc++.h>
using namespace std;
int dp[100005];
int main(){
    int n;
    cin >> n;
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2;i <= n;i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
}

有些題目某種會好寫很多，就是樹 DP top-down 就會好寫很多，只是因為 top-down 要用到遞迴，所以速度可能會比 bottom up 慢。

當然，DP 完全不只那麼簡單，很多時候它的狀態跟遞迴關係式都可以變得非常複雜。

例題

我們用 AtCoder 的 A – Frog 1 題當作例子。我們的狀態可以設定成 dp[i] = 走到第 i 格需要的最小花費
在動態規劃時，我們常常用 dp 直接叫做陣列名字 (當然不一定要，只是通常都這樣寫）。在定義狀態時，你要想想怎麼把原本的問題分成可以解決並且把答案儲存下來的小問題。

我們可以想想，假如我現在在第 i 格，我可以從甚麼狀態轉移過來? 因為題目說每一步你可以走一格或是兩格，所以要走到第 i 格，上一步一定是要從第 i -1 格或是 i – 2 格過來!

於是，我們知道 dp[i] 會從 dp[i-1] 跟 dp[i-2] 過來，接下來我們就要考慮要怎麼透過這兩個子問題的答案計算出 i 的答案。依照題目，從 i – 1 格到 i 所需的花費會是兩個的高度差，也就是 abs (a[i] – a[i-1])。所以，我們從 i – 1 轉移過來的花費就會是 dp[i-1] + abs(a[i] – a[i-1]) ! 也就是 (從 0 ~ i-1 最小花費) + (從 i-1 到 i 的花費)
而 i – 2 也是依樣的道理，於是我們就可以得到轉移式 

dp[i] = min(dp[i-1]+abs(a[i-1]-a[i]), dp[i-2]+abs(a[i-2]-a[i]));

最後，我們需要想一下 dp 狀態的初始條件。這題的話，題目說青蛙從第一格開始跳，所以 dp[1] = 0，因為從 0 到 0 不需要任何花費，而其他都應該先設成無限大，因為我們現在還沒辦法從 0 走到其他格子。不過在這題來說，其實也不需要，因為我們從 0 往上慢慢更新，不會遇到走不到的問題。但是在有些題目，就要注意初始狀態有沒有設定好。

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin >> n;
    vector <int> a(n);
    for(int &x : a) cin >> x;
    vector <int> dp(n);
    dp[1] = abs(a[1]-a[0]);
    for(int i = 2;i < n;i++){
        dp[i] = min(dp[i-1]+abs(a[i-1]-a[i]), dp[i-2]+abs(a[i-2]-a[i]));
    }
    cout << dp[n-1] << '\n';
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
}

動態規劃就差不多是這樣！動態規劃最重要的就是，要寫很多題目，看看很多不同的題型。動態規劃是我認為真的，唯一能靠練習題目才能進步的主題，因為它的變化有非常多。我建議把 CSES DP Section 以及上面例題用到的 Atcoder Educational DP Contest 開始寫，這兩個題庫都很經典也都很有幫助！

在WordPress.com寫網誌.