---
tags: APCS Preparation
---
# Dynamic Programming
## Maximum Subarray
### Problem Statement
給定一個陣列有10個元素，請找出最大的連續子陣列和，結果會在$-10^8$到$10^8$之間，陣列元素不會都是小於0的數字
### Sample I/O
Input
```
1 2 3 4 5 -10 20 30 -40 10
```
Output
```
55
```
### 解題想法
加總到sum < 0 時，該結果沒有幫助
所以歸零後再繼續加，如果新的加總結果比原本的max還要大 -> 更新max值
```cpp
#include <iostream>
using namespace std;
int main()
{
int arr[10];
while(1)
{
for(int i=0;i<10;i++)
{
cin>>arr[i];
}
int max = -200000000;
int sum = 0;
for(int i=0;i<10;i++)
{
sum+=arr[i];
if(sum>max)
{
max = sum;
}
if(sum<0)
{
sum = 0;
}
}
cout<<max<<endl;
}
}
```
## 01 Knapsack Problem
### Problem Statement
假設有n個物品跟一個背包，已知背包的負重能力與每個物品的價值與重量，物品只能取或不取，不能只取物品的一部分，且每樣物品只有一個，求在書包的負重能力範圍內放入背包所有物品的最大價值
###
```cpp
#include<iostream>
#include<cstdlib>
using namespace std;
int v[101],w[101],k[1001];
int ks,n;
int main()
{
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>w[i]>>v[i];
}
cin>>ks;
memset(k, 0, sizeof(k));
for(int i=0;i<n;i++)
{
for(int j=ks;j>=w[i];j--) //必須要大於等於w[i]的才能討論
{
if(k[j-w[i]]+v[i]>k[j])
{
k[j] = k[j-w[i]]+v[i];
}
}
}
cout<<"max_val:"<<k[ks]<<endl;
}
}
```
## 01 Knapsack Problem 考慮最佳解路徑
```cpp
#include<iostream>
using namespace std;
int v[101],w[101],k[1001],p[101][1001];
int ks,n; //maximum_weight
int main()
{
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>w[i]>>v[i];
}
cin>>ks;
memset(k,0,sizeof(k));
memset(p,-1,sizeof(p));
for(int i=0;i<n;i++)
{
for(int j=ks;j>=w[i];j--)
{
if(k[j-w[i]]+v[i]>k[j])
{
k[j] = k[j-w[i]] + v[i];
p[i][j] = i;
}
}
}
cout<<"書包的最大價值為"<<k[ks]<<endl;
//取得放書包路徑
int j = ks;
for(int i=n-1;i>=0;i--)
{
if(p[i][j]>=0)
{
cout<<"put "<<i+1<<" th item into the knapsack"<<endl;
j = j - w[i];
}
}
}
}
```
## Money Changing Problem
### Problem Statement
某國家有n個硬幣面額，請你計算達成目標金額x的最少硬幣個數，所輸入的n種硬幣面額一定可以達成目標金額x
### Input
每次輸入數字n，n表示硬幣面額個數，n小於10，之後n後每一行分別有一個整數v，表示硬幣的面額。最後輸入一個整數x，表示目標金額，且x小於50000
### Output
輸出一個整數，表示達成目標金額x的最少硬幣個數
### Sample Input
4
4
1
9
12
20
### Sample Output
4
```cpp
#include<iostream>
#include<cstdlib>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
int v[n],x;
for(int i=0;i<n;i++)
{
cin>>v[i];
}
cin>>x;
int m[50001];
memset(m,0x6f,sizeof(m));
m[0] = 0;//初始化～重要！
for(int j=0;j<n;j++)
{
for(int r=v[j];r<=x;r++)
{
m[r] = min(m[r],m[r-v[j]]+1); //加入此貨幣跟不加入方法數的min
}
}
cout<<m[x]<<endl;
}
}
```
```cpp
//考慮路徑時的解法
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
int m[50001],p[50001];
int v[1001],x;
int main()
{
int n;
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>v[i];
}
cin>>x;
memset(m,0x6f,sizeof(m));
memset(p,0,sizeof(p));
m[0] = 0;
for(int j=0;j<n;j++)
{
for(int r=v[j];r<=x;r++)
{
if(m[r] > m[r-v[j]]+1)
{
//cout<<"ready!"<<endl;
p[r] = v[j];
}
m[r] = min(m[r],m[r-v[j]]+1);
}
}
cout<<m[x]<<endl;
int tmp = x;
while(tmp>0)
{
cout<<p[tmp]<<" ";
tmp-=p[tmp];
}
cout<<endl;
}
}
```
## Longest Common Subsequence
### Input
每次輸入兩個英文字串，求這兩個字串的最長共同子序列，兩字串長度都不會超過 100 chars
### Output
輸出一個整數，表示lcs長度
### Sample Input
```
comp
zope
```
### Sample Output
```
2
```
### 解題思路
> 參考來源：http://web.ntnu.edu.tw/~algo/LongestCommonSubsequence.html
有兩字串s1, s2 要找出兩字串的LCS，記為LCS(s1,s2)
取出兩字串最後一個元素
> $i.e.$
> $s_{1} = sub_{1} + e_1$
> $s_2 = sub_2 + e_2$
分情形討論
| 情形 | $lcs(s1,s2)$ |
| ------------------- |:--------------------:|
| LCS包含e1，不包含e2 | $lcs(s1,sub_2)$ |
| LCS包含e2，不包含e1 | $lcs(sub_1,s2)$ |
| LCS不包含e1和e2 | $lcs(sub_1,sub_2)$ |
| LCS包含e1且e2 | $lcs(sub_1,sub_2)+1$ |
統整
```cpp
LCS(s1, s2) =
{ max( LCS(sub1, s2), LCS(s1, sub2) ) , when e1 != e2
{ LCS(sub1, sub2) + e1 , when e1 == e2
```
```cpp
#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;
int main ()
{
string a,b;
while(1)
{
getline(cin,a);
getline(cin,b);
long int s1 = a.length();
long int s2 = b.length();
int lcs[s1+1][s2+1];
memset(lcs, 0, sizeof(lcs));
lcs[0][0] = 0;
for(int i=0;i<s1;i++)
{
for(int j=0;j<s2;j++)
{
if(a[i] == b[j])
{
lcs[i+1][j+1] = lcs[i][j] + 1;
}
else
{
lcs[i+1][j+1] = max(lcs[i+1][j],lcs[i][j+1]);
}
}
}
cout<<lcs[s1][s2]<<endl;
}
}
```
```cpp
//包含輸出該lcs
#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;
int main()
{
string s1,s2;
while(1)
{
getline(cin,s1);
getline(cin,s2);
long long int len1 = s1.length();
long long int len2 = s2.length();
int lcs[len1+1][len2+1];
memset(lcs,0,sizeof(lcs));
lcs[0][0] = 0;
string r = "";
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
if(s1[i] == s2[j])
{
lcs[i+1][j+1] = lcs[i][j]+1;
r+=s1[i];
}
else
{
lcs[i+1][j+1] = max(lcs[i+1][j],lcs[i][j+1]);
}
}
}
cout<<lcs[len1][len2]<<endl;
cout<<r<<endl;
}
}
```
Sign in with Wallet
Connect another wallet