---
# System prepended metadata

title: Dynamic Programming
tags: [Coding]

---

---
tags: Coding
---
# Dynamic Programming

**核心概念:**
**重複利用陣列 以空間換取時間** 
**一個一個慢慢塞 嘗試到最後**

## 1.硬幣問題
假如我們有1 3 5硬幣的面額，要湊成10塊。
而湊成10塊的方式有:
1 1 1 1 1 1 1 1 1 1
3 1 1 1 1 1 1 1 
3 3 1 1 1 1
3 3 3 1
5 3 1 1
5 5

今天我有 1, 5, 10, 25, 50 面額的硬幣
有幾種方法可以將金額 11元找錢出來？
因為之前都已經先記錄過每一個金額的可能種類，所以當我們遇到新的硬幣時，就可以直接用現在的金額去減新的硬幣，11-10 = 1，也就是用 10那格a目前的最大可能種類，再加上1元的可能種類。
10元的可能種類數是：3（也就是截至目前只包含到 1, 5兩個硬幣種類有3種狀況，請參考上圖）

此題我們用迴圈個別把每塊錢有可能的方法依序用1 3 5元去試
1塊錢就只有一個可能
而三塊就是先塞一個，然後繼續下去跑迴圈它會再繼續塞三塊硬幣下去，因為前面有塞過就會再塞一個。然後跑到最大才結束。倒數幾行的j-coins[i]就是塞硬幣的意思。

```cpp=
#include<iostream>
using namespace std;

int main()
{
        int coins[4] = {1, 5, 10, 50};
        int price = 0;
	cin >> price;
	
	// 先初始化，可能種類陣列
	int arr[price + 1];
	for(int i = 0; i < price + 1; ++i)
		arr[i] = 0;

	//金額為零時，只又一種可能，不放錢進去
	arr[0] = 1;
	
	for(int i = 0; i < 4; ++i)
	{
		for(int j = coins[i]; j < price+1; j++)
			arr[j] = arr[j] + arr[j - coins[i]];
	}
	cout << arr[price] << endl;
}
```
## 0/1背包問題
[ZJ題目](https://zerojudge.tw/ShowProblem?problemid=b184)
<img loading="lazy" width="1024" height="548" src="https://yuihuang.com/wp-content/uploads/2020/01/0-1-knapsack-2-1024x548.png" alt="" class="wp-image-4894" srcset="https://yuihuang.com/wp-content/uploads/2020/01/0-1-knapsack-2-1024x548.png 1024w, https://yuihuang.com/wp-content/uploads/2020/01/0-1-knapsack-2-300x160.png 300w, https://yuihuang.com/wp-content/uploads/2020/01/0-1-knapsack-2-768x411.png 768w, https://yuihuang.com/wp-content/uploads/2020/01/0-1-knapsack-2.png 1393w" sizes="(max-width: 1024px) 100vw, 1024px">
為了計算方便第一行放重量價值為0，第一列是當重量為0時的最大價值。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int dp(vector<int>v,vector<int>c,vector<vector<int>> arr,int n){
    int maxN=0;
    for(int i=0;i<n;i++){
        for(int j=1;j<=100;j++){
            if(j-v[i]>=0){
                arr[i+1][j]=max(arr[i][j-v[i]]+c[i],arr[i][j]);
                maxN=max(maxN,arr[i+1][j]);
            }else{
                arr[i+1][j]=arr[i][j];
            }
        }
    }
    return maxN;
}
int main(){
    int n;
    while(cin>>n){
        vector<int> v(n);
        vector<int> c(n);
        vector<vector<int>> arr(1000,vector<int>(105));
        for(int i=0;i<n;i++){
            cin>>v[i]>>c[i];
        }
        cout<<dp(v,c,arr,n)<<endl;
    }
    return 0;
}
```
## lcs最大共同字串
https://www.youtube.com/watch?v=WKzV8AthfmM
題目 https://zerojudge.tw/ShowProblem?problemid=c001

找的邏輯是依照以下第一張去對照，然後產生第二張圖。找的方法是對照看有一樣的話就看左上角，不然就看上或是左哪個比較大。

![](https://hackmd.io/_uploads/SJxBVg-r3.jpg)

![](https://hackmd.io/_uploads/B1xSElWSn.jpg)
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
int length[1000][1000]={0};
int dp(string s1,string s2){
    int len1=s1.size();
    int len2=s2.size();
    for(int i=1;i<len1;i++){
        for(int j=1;j<len2;j++){
            if(s1[i]==s2[j])length[i][j]=length[i-1][j-1]+1;
            else length[i][j]=max(length[i-1][j],length[i][j-1]);
        }
    }
    return length[len1-1][len2-1];
}
signed main(){
    string s1,s2;
    while(cin>>s1>>s2){
        cout<<dp("0"+s1,"0"+s2)<<endl;
    }
    return 0;
}

```
## 找最大值的路徑
### 巴比倫塔
https://zerojudge.tw/ShowProblem?problemid=c115
![](https://hackmd.io/_uploads/rJt2QgdE3.jpg)
畫成圖大概長這樣就是個一個去比然後更新裡面的值
```cpp=
#include <bits/stdc++.h>
#define int long long
#define pb push_back

using namespace std;

struct side {
    int s1, s2, s3;
};

void dp(vector<side> arr, int highest) {
    const int n = arr.size();
    int MAX = 0;
    int sum[n];
    for (int i = 0; i < n; i++) sum[i] = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[j].s2 > arr[i].s2 && arr[j].s3 > arr[i].s3) {
                if (sum[j] == 0) {
                    sum[j] = arr[i].s1 + arr[j].s1;
                    MAX = max(MAX, sum[j]);
                } else {
                    sum[j] = max((arr[j].s1 + sum[i]), sum[j]);
                    // sum[j] += arr[i].s1;
                    MAX = max(MAX, sum[j]);
                }
            }
        }
    }
    if (MAX == 0)
        cout << highest << endl;
    else
        cout << MAX << endl;
}

int cmp(side a, side b) {
    if (a.s2 == b.s2)
        return a.s3 < b.s3;
    else
        return a.s2 < b.s2;
}

int uni_cmp(side a, side b) {
    if (a.s1 == b.s1 && a.s2 == b.s2 && a.s3 == b.s3)
        return 1;
    else
        return 0;
}

signed main() {
    int n, cnt = 1;
    while (cin >> n) {
        int highest = 0;
        if (n == 0) break;
        vector<side> arr;
        for (int i = 0; i < n; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            highest = max(max(a, b), c);
            arr.pb((struct side){a, min(b, c), max(b, c)});
            arr.pb((struct side){b, min(a, c), max(a, c)});
            arr.pb((struct side){c, min(a, b), max(a, b)});
        }
        arr.erase(unique(arr.begin(), arr.end(), uni_cmp), arr.end());
        sort(arr.begin(), arr.end(), cmp);
        cout << "Case " << cnt << ": maximum height = ";
        cnt++;
        dp(arr, highest);
    }
    return 0;
}
```
### 摩天大樓
https://zerojudge.tw/ShowProblem?problemid=e686
也是用一樣的方法只是比較方式不同
```cpp=
#include <bits/stdc++.h>
using namespace std;

struct adv {
    int l, r, val;
};

int solve(vector<adv> arr, int MAX) {
    int n = arr.size();
    int sum[n];
    memset(sum, 0, sizeof(sum));
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i].r < arr[j].l || arr[j].r < arr[i].l) {
                if (sum[j] == 0) {
                    sum[j] += arr[i].val + arr[j].val;
                    MAX = max(MAX, sum[j]);
                } else {
                    sum[j] = max(sum[i] + arr[j].val, sum[j]);
                    MAX = max(MAX, sum[j]);
                }
            }
        }
    }
    return MAX;
}

bool cmp(adv a, adv b) {
    return a.l < b.l;
}

int main() {
    int n;
    cin >> n;
    for (int j = 0; j < n; j++) {
        int m;
        int MAX = 0;
        cin >> m;
        vector<adv> arr;
        for (int i = 0; i < m; i++) {
            adv a;
            cin >> a.l >> a.r >> a.val;
            a.r = a.l + a.r - 1;
            arr.push_back(a);
            MAX = max(MAX, a.val);
        }
        sort(arr.begin(), arr.end(), cmp);
        cout << "Case " << j + 1 << ": " << solve(arr, MAX) << endl;
    }
    return 0;
}
```