---
# System prepended metadata

title: Dynamic Programming
tags: [APCS Preparation]

---

---
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;
    }
    
}

```