Dynamic Programming

以空間換取時間 by 蔣介石/白崇禧

slido

https://app.sli.do/event/76TUgLn8RkpK64FQMTc6Ve

概念

動態規劃為分治法的延伸，都是藉由子問題答案合併出當前問題的答案。

並將會重複計算的部分運用記憶體儲存起來，來避免重複計算
ex.圖中f(18)計算了兩次，因此f(16)計算了四次，f(17)計算了三次…

費式數列

費式數列為動態規劃最基本的例子

定義:

f(1)=1
f(2)=1
f(n)=f(n-1)+f(n-2), if n>2

題目:求費式數列的第k項

相信這對學會遞迴的你們，根本 a piece of cake!

int f(int i){
    if(i==1 or i==2) return 1;
    else return f(i-1)+f(i-2);
}

複雜度

$O(2^n)$

優化(Top-Down)

int temp[10000]={};
int f(int i){
    if(temp[i]>0) return temp[i]; //temp[i] 已經算過了
    if(i==1 or i==2) temp[i]=1;
    else temp[i]=f(i-1)+f(i-2);
    return temp[i];
}
int main(){
    cout<<f(k);
}

變成O(n)了!

你會發現，每次要為f[i]賦值時，只會動用i前面的答案。
利用這點，能不能寫出不用遞迴函數的寫法呢?

Bottom-Up

int f[n+1]={};
for(int i=1;i<=n;i++){
    if(i<=2) f[i]=1;
    else f[i]=f[i-1]+f[i-2];
}
cout<<f[k]<<endl;

根據答案轉移的方向，選擇一個迴圈方向，使得每次呼叫f[j]時，他都已經算好答案了!

小結論

動態規劃的精隨，是狀態及轉移
利用前面已知的答案推出現在的答案，再給未來的人利用我推出未來的答案

定義 dp[狀態] 來表示，在此狀態的答案
而轉移的過程可能會長這樣:

dp[狀態]=dp[???]+bla bla bla…

就像數學的遞迴式一樣。
所以初學者寫DP的時候，先想要怎麼列遞迴式，再想如何用程式實現

思考流程

0. 通靈
1. 找出dp各個所對應的狀態(維度所代表的值) ex.f(n)=費式數列的第
   $n$項
2. 找出轉移式(狀態之間的關係) ex.f(n)=f(n-1)+f(n-2), if n>2
3. 設定初始值 ex.f(1)=1 f(2)=1

青蛙跳問題

$N$ 個石頭，編號為

$1,2,...,N$。 對於每個

$i(1\le i\le N)$，石頭

$i$ 的高度為

$h_i$。

原本有一隻青蛙在石頭

$1$ 上。 他將重複幾次以下操作以到達石頭

$N$：

• 如果青蛙目前在石頭
  $i$ 上，則跳到石頭
  $i+1$ 或石頭
  $i+2$。 需要
  $|h_i-h_j|$ 的費用，而
  $j$ 是要落到上面的石頭。

找到青蛙到達石頭

$N$ 之前所需的最小總費用。

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&h[i]);
	dp[1]=0;
	dp[2]=abs(h[1]-h[2]);//初始化，2號石頭只能從前一塊（1號）石頭跳來
	
	for(int i=3;i<=n;i++)
		dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
	
	printf("%d",dp[n]);
	return 0;
}

題目

Frog A
Frog B
d066: P-6-1. 小朋友上樓梯最小成本

C - Vacation

都說是

$dp$ 了，來想一下

$dp$ 式吧
如果這回合要游泳，則上個回合只能抓蟲或寫功課
如果能記錄上回合做三種動作分別的最大快樂度呢?

定義

$dp[i][j]$ 為第

$j$ 回合做第

$i$ 種動作的最大快樂度

$0,1,2$ 代表

$A,B,C$
則有轉移式

$dp[0][j]=max(dp[1][j-1],dp[2][j-1])+a[j]$

$dp[1][j]=max(dp[0][j-1],dp[2][j-1])+b[j]$

$dp[2][j]=max(dp[0][j-1],dp[1][j-1])+c[j]$

而最後的答案會是

$max(dp[0][n],dp[1][n],dp[2][n])$

code:

long long n;
cin >> n;
vector<long long> a(n), b(n), c(n);
vector<vector<long long>> dp(3, vector<long long>(n));
for (int i = 0; i < n; i++)
{
    cin >> a[i] >> b[i] >> c[i];
}
dp[0][0] = a[0];//初始化
dp[1][0] = b[0];
dp[2][0] = c[0];

for (int i = 1; i < n; i++)
{
    dp[0][i] = max(dp[1][i - 1], dp[2][i - 1]) + a[i];
    dp[1][i] = max(dp[0][i - 1], dp[2][i - 1]) + b[i];
    dp[2][i] = max(dp[0][i - 1], dp[1][i - 1]) + c[i];
}

cout << max({dp[0][n - 1], dp[1][n - 1], dp[2][n - 1]}) << endl;

d069: P-6-6. 方格棋盤路線

應該很簡單吧
因為要走到

$(i,j)$ 一定是從

$(i-1,j)$ 或

$(i,j-1)$ 來
定義

$dp[i][j]$ 為走到

$(i,j)$ 時的最大得分
則有轉移式

$$dp[i][j]=max(dp[i-1][j],dp[i][j-1])+value[i][j]$$
答案為

$dp[m-1][n-1]$

注意邊界!!!

題目

Grid1 新增障礙物

背包問題

0-1 背包

題目大意:有一個能裝總重

$w$ 的背包和

$m$ 種商品，每種商品都有一個價值和重量，
問這個背包的最大價值?
當然並不總是重量和價值，例如 這題 和 這題
總之概念都差不多

為了方便說明，以下面這題為例
D - Knapsack 1

直接破梗:

$n$ 個物品，背包最大載重為

$w$
定義

$dp[i][j]$ 為選前

$i$ 個物品，背包最大載重為

$j$ 時的最大價值
從第一個物品跑到最後一個
對於第

$i$ 個物品

不拿:

$$dp[i][j]=dp[i-1][j],\mathrm{\forall }j\in [0,w]$$
拿:

$$dp[i][j]=(dp[i-1][j-weight[i]])+value[i],\mathrm{\forall }j\in [weight[i],w]$$
對 拿/不拿 兩種情況取最大值
最後答案為

$dp[n][w]$

code:

int n, w;
cin >> n >> w;
vector<int> weight(n + 1), value(n + 1);
for (int i = 1; i <= n; i++)
{
    cin >> weight[i] >> value[i];
}
int dp[n + 1][w + 1] = {};
for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= w; j++)
    {
        if (j - weight[i] >= 0)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
        else
        {
            dp[i][j] = dp[i - 1][j];
        }
    }
}
cout << dp[n][w] << endl;

時間複雜度為

$\mathcal{O}(nw)$
空間複雜度為

$\mathcal{O}(nw)$

優化 (滾動)

注意到轉移來源只有上一輪的

$dp$
所以可以改成只開兩個陣列，一個是現在的，一個是上一輪的
做完之後把這輪的變成上一輪，一直做下去
時間複雜度為

$\mathcal{O}(nw)$
空間複雜度為

$\mathcal{O}(w)$
code:

long long n, w;
cin >> n >> w;
vector<long long> weight(n), value(n);
for (int i = 0; i < n; i++)
{
    cin >> weight[i] >> value[i];
}
long long dp1[w + 1] = {}, dp2[w + 1] = {};
for (int i = 0; i < n; i++)
{
    for (int j = 0; j <= w; j++)
    {
        if (j - weight[i] >= 0)
        {
            dp2[j] = max(dp1[j], dp1[j - weight[i]] + value[i]);
        }
    }
    for (int j = 0; j <= w; j++)
    {
        dp1[j] = dp2[j];
    }
}
cout << dp1[w] << endl;

又注意到轉移來源總是在自己左方
所以可以由後往前做
這樣只需要開一個一維陣列
時間複雜度為

$\mathcal{O}(nw)$
空間複雜度為

$\mathcal{O}(w)$
code:

long long n, w;
cin >> n >> w;
vector<long long> weight(n), value(n);
for (int i = 0; i < n; i++)
{
    cin >> weight[i] >> value[i];
}
long long dp[w + 1] = {};
for (int i = 0; i < n; i++)
{
    for (int j = w; j - weight[i] >= 0; j--)
    {
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
cout << dp[w] << endl;

變體

有限背包Book Shop II

LCS

LCS-atcoder
LCS (Longest common subsequence)
兩字串的最長共同子序列
子序列 : 某個序列的子序列是從最初序列通過去除某些元素但不破壞餘下元素的相對位置（在前或在後）而形成的新序列。

a: "algorithm"
b: "alignment"

LCS(a, b): "algm" or "algt"

破梗:
定義

$dp[i][j]$ 為

$a[0,i]$ 和

$b[0,j]$ 的 LCS 長度

如果

$a[i]=b[j]$ :

$$dp[i][j]=dp[i-1][j-1]+1$$
如果

$a[i]\ne b[j]$ :

$$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$$
稍微想一下，應該滿直覺的 (?)

code:

string a, b;
cin >> a >> b;
int n = a.length(), m = b.length();
int dp[m + 1][n + 1] = {};
for (int i = 1; i <= m; i++)
{
    for (int j = 1; j <= n; j++)
    {
        if (a[j - 1] == b[i - 1]) // 0-based string
        {
            dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        else
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
}
cout << dp[m][n] << endl;

題目

Atcoder Educational DP Contest
有 26 題

$dp$，這個有按照難度排

DP on CSES
有 19 題

$dp$ ，都是滿經典的題型

DP on CodeForces
有數以百計的

$dp$ ，有些甚至不需要

$dp$

DP on TCIRC (AP325)
是中文的，而且 AP325 不刷嗎?

Refernce

111學年度資訊讀書會DP講義
https://alanlee.fun/2020/04/07/understanding-lcs/
https://www.javatpoint.com/dynamic-programming