---
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
找的邏輯是依照以下第一張去對照，然後產生第二張圖。找的方法是對照看有一樣的話就看左上角，不然就看上或是左哪個比較大。
```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
畫成圖大概長這樣就是個一個去比然後更新裡面的值
```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;
}
```
Sign in with Wallet
Connect another wallet