基礎動態規劃

基本觀念

動態規劃(Dynamic Programming, DP)

Dynamic的意思是動態的，而Programming則是以表格紀錄，所以DP其實就是以變動的表格來求解。

DP的應用很廣、變化很多，在程式競賽中常常遇到這類題目，而且DP有許多困難而精妙的(變態)優化方法，很多題目都需要花時間好好體會，所以此章只會先介紹一些典型的例題，後續的變化及優化方法將在進階動態規劃討論。

想法

動態規劃和分治法相同，都是將問題分成子問題，再將子問題的解合併成最後的解，設計DP都是從尋找遞迴式開始，大致可分為三步驟。

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;
}

這程式可以跑，只要不輸入太大的數字，因為這遞迴函式會一個呼叫兩個，兩個呼叫四個，複雜度接近2的N次方。

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

觀察上圖之例子可知，我們其實重複執行了需多運算，如果能將每次運算的值都處存下來，便可節省許多的運算時間，這時我們可以將程式改寫如下。

#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;
}

透過一個dp[]陣列將運算過後的值存起來，並以-1來表示此數值還未計算過，但透過觀察可發現第n項的值是由n-1項和n-2項所構成的，那麼就可以用一個for迴圈由小到大計算數值來求第n項的值，進而縮減成下列程式碼:

#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;
}

那麼，在了解DP的基礎概念後，就能進入一系列的例題了。

例題1

題目連結：Frog1
思路：這題最主要的思路定義一狀態dp(i)為走到第i格時
程式碼：

例題２

題目連結：Frog２
思路：
程式碼：

1D1D

2D1D

習題

tags: APCS與競賽入門