---
title: dp動態規劃
type: slide
---

dp動態規劃
===

----

#### 什麼是DP(Dynamic Programming)?

----

DP又被稱為動態規劃
透過把大問題拆成較簡單的子問題
求解複雜問題的方法

----

dp利用記錄每個小問題的答案
減少重複計算
快速地找出最終的解

----

在寫dp時
我們要考慮兩個東西
__邊界條件__ 和 __轉移式__
在接下來會詳細說明

---

### 線性dp

----

線性dp是學dp的起點
在這裡我們再拿費氏數列來舉例

----

### 費氏數列
$f(n)=f(n-1)+f(n-2)$ n>=2
$f(0)=1$ $f(1)=1$

----

在費氏數列中
他的邊界條件就是
$dp[0]=1$
$dp[1]=1$
轉移式就是
$dp[i]=dp[i-1]+dp[i-2]$

----

實際寫出來就會長這樣

int dp[20005];
dp[0]=1;
dp[1]=1;
for(int i=2;i<=n;i++)
    dp[i]=dp[i-1]+dp[i-2];
cout<<dp[n];

----

除了剛才那種寫法
我們還能用遞迴來寫

----

int dp[200005];
int fibo(int i){
    if(i==0 or i==1) return 1;
    if(dp[i]) return dp[i];
    return dp[i]=fibo(i-1)+fibo(i-2);
}

---

剛才那兩個寫法
一種叫buttom-up
另一種叫top-down
兩種寫法各有優缺點

----

### buttom-up
buttom-up通常用for迴圈來寫
顧名思義是從下到上來找出答案
優點是較遞迴來的快
缺點是沒那麼直觀
大部分的人dp都用這種方法來解

----

### top-down
top-down一樣從名字來看就是從上到下
通常用遞迴來寫
優點是較直觀
缺點是多次呼叫函式會浪費時間

---

### 練習題
[爬樓梯問題之一](http://mdcpp.mingdao.edu.tw/problem/A048)
[爬樓梯問題之二](http://mdcpp.mingdao.edu.tw/problem/A049)
[爬樓梯問題之三](http://mdcpp.mingdao.edu.tw/problem/A050)

---

dp也能處理 __尋照最佳解的問題__
拿[P-4-13. 最大連續子陣列](https://judge.tcirc.tw/ShowProblem?problemid=d052)來做講解

----

這題說給一個陣列
要找出總和最大的連續子陣列
我們來想想有什麼辦法

----

在還沒學dp前
我們只能枚舉所有左界和右界
列出所有可能後加起來
如果不用前綴和
時間複雜度會來到$O(N^3)$
就算用了複雜度只會降到$O(N^2)$
$N$最大是$10^5$所以會 __TLE__

----

這時候我們就可以用dp了
首先要想
$dp[i]$所代表的意義

----

假設我們讓$dp[i]$的值是 __到$i$為止最大連續子陣列的和__
那你會發現你想不出轉移式

----

所以我們要讓$dp[i]$是 __以$i$結尾最大的連續子陣列__
這樣的話轉移式就是
$dp[i]=max(dp[i-1]+a[i],a[i])$
邊界條件就是
$dp[0]=0$
時間複雜度是$O(N)$

----

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);//IO優化
	int n,a[N],dp[N];
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	dp[0]=0;//邊界條件
	for(int i=1;i<=n;i++){
		dp[i]=max(dp[i-1]+a[i],a[i]);//轉移式
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		ans=max(ans,dp[i]);//找最大值
	cout<<ans;
}

---

## 二維DP

----

二維dp就是dp那個陣列變二維
來看一下這個題目[採果實問題](http://mdcpp.mingdao.edu.tw/problem/A052)

----

用dp來想
$dp[i][j]$代表走到i,j時能採到最多個果實數
邊界條件就都設0
轉移式是$dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]$

----


----

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200+5;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);//IO優化 
	int n,a[N][N],dp[N][N]={0};
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];//轉移式
	
	cout<<dp[n][n];
}

----

### 練習題
[方格棋盤路線](https://judge.tcirc.tw/ShowProblem?problemid=d069)
[投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373)

---

### 背包DP
背包dp有

- 01背包
- 有限背包
- 無限背包
...很多種
我們這次先講01背包

----

01背包基本上會給
- 背包容量
- 物品重量
- 物品價值
最後會問裝出價值最高的價值

----

範例題
[裝貨櫃問題](https://zerojudge.tw/ShowProblem?problemid=b184)

----

最簡單的方法就是用暴力枚舉
每種物品可拿可不拿
所以有$2^N$種可能
時間複雜度$O(2^N)$
N到26就不行了

----

這時候就要用dp了
我們開一個二維dp
$dp[i][j]$代表
考慮到第$i$種物品時
最大容量為$j$時能裝的最大利潤

----

轉移式：
$dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])$

$w[i]$為第$i$項物品的重量
$v[i]$為第$i$項物品的價值
須注意$j-w[i]$可能小於0所以前面需要加條件式
避免溢位

----

code

#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n){
		vector<int> v(n+1),w(n+1);
		vector<vector<int> > dp(n+1,vector<int>(101));
		for(int i=1;i<=n;i++){
			cin>>w[i]>>v[i];
		}
		for(int i=1;i<=n;i++){
			for(int j=0;j<=100;j++){
				if(j-w[i]>=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
				else dp[i][j]=dp[i-1][j];
			}
		}
		cout<<dp[n][100]<<"\n";
	}
}

---

### 背包dp優化

----

其實背包dp不用開到2維
開一維就夠了
只是這樣遍歷容量時要倒著走

----

code

#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n){
		vector<int> v(n+1),w(n+1);
		vector<int> dp(101);
		for(int i=1;i<=n;i++){
			cin>>w[i]>>v[i];
		}
		for(int i=1;i<=n;i++){
			for(int j=100;j>0;j--){
				if(j-w[i]>=0) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
			}
		}
		cout<<dp[100]<<"\n";
	}
}

----

### 練習題
[置物櫃出租](https://judge.tcirc.tw/ShowProblem?problemid=d075)
[D - Knapsack 1](https://atcoder.jp/contests/dp/tasks/dp_d)