# DP學習筆記
[toc]

## 背包問題
現在有 n 個物品，第 i 個物品的重量和價值分別是 w_i 和 v_i，妳的背包最多可以裝 W 的重量， 問能裝進背包的最大價值為何?

$1 \le n \le 100$
$1 \le w_i \le W \le 10^5$
$1 \le v_i \le 10^9$

**解法:**
在前i個物品中，重量為$w$的最大價值為何？

$F(i, w) = \text{max}(\space F(i - 1, w), F(i-1, w-w_i\space) + v_i)$

選:

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define endl "\n";

int n, max_w, t1, t2;
vector<pair<lint, lint>> vec; // weight, value
vector<vector<lint>> dp(1000, vector<lint>(100010, -1));

lint f(lint i, lint w)
{
    if(i == -1 || w < 0) return 0;

    if(dp[i][w] != -1)
    {
        return dp[i][w];
    }
    else
    {
        lint choose = 0;
        lint not_choose = f(i-1, w);
        if(w - vec[i].first >= 0)
        {
            choose = f(i-1, w - vec[i].first) + vec[i].second;
        }
        dp[i][w] = max(choose, not_choose);
        return dp[i][w];
    }
}

int main()
{
    cout.sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> max_w;

    for (int i = 0; i < n; i++)
    {
        cin >> t1 >> t2;
        vec.emplace_back(t1, t2);
    }

    cout << f(n-1, max_w);
}

## 消除位數
給一個數字 n，每次操作可以減掉 n 的某個 位數 的值。問最少要幾次操作才能讓 n 歸零

$1 \le n \le 10^6$

**解法:**

$F(0) = 0$
$F(i) = \text{min}(\space f(i - d) + 1 \space)$, $d$ 是 $i$ 的位數

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define endl "\n";

vector<int> dp((int)1e6 + 10, -1);

// 當前數字為 i 時，減位數到 0 的最小步數
int f(int i)
{
    if(i <= 0) return 0;
    
    if(dp[i] != -1)
    {
        return dp[i];
    }
    else
    {
        string string_i = to_string(i);
        int count = string_i.size(); // 得到 string_i 的位數
        int min = (int)1e8, current_num;
        for (int j = 0; j < count; j++)
        {
            if(string_i[j] == '0')
                continue;

            current_num = f(i - (string_i[j] - '0')) + 1;

            if(current_num < min)
            {
                min = current_num;
            }
        }

        dp[i] = min;
        return dp[i];
    }
}

int main()
{
    cout.sync_with_stdio(false);
    cin.tie(nullptr);

    int i;
    cin >> i;
    cout << f(i);

}

## 找零問題

### Minimizing Coins 湊錢問題

給定 𝑛 種面額不同的錢幣，問要湊出 𝑥 元最少需要幾個錢幣？

$1 \le n \le 100$
$1 \le x \le 10^6$
$1 \le c_i \le 10^6$

**解法**:

湊出 i 元最少需要幾個硬幣
$F(i) = \text{min}(\space F(i - c_i) \space) + 1$

**範例**:
湊出 5 元最少需要幾個硬幣(2元,3元)

湊出 5 元 =>拿2元 => 湊出 3 元 => 拿2元 => 湊出 1 元 => 不可能
=========================> 拿3元 => (2枚)

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define endl "\n";
#define INF (int)1e7 + 10

vector<int> vec;
vector<int> dp((int)1e6 + 10, -1);

int n, target, t;

// 湊出 i 元最少需要幾個硬幣
int f(int i)
{
    if(i == 0) return 0;
    if(i < 0) return INF;

    if(dp[i] != -1)
    {
        return dp[i];
    }
    else
    {
        int ans = INF;
        for (int j = 0; j < n; j++)
        {
            ans = min(f(i - vec[j]) + 1, ans);
        }

        dp[i] = ans;
        return dp[i];
    }
}

int main()
{
    cout.sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> target;

    for (int i = 0; i < n; i++)
    {
        cin >> t;
        vec.emplace_back(t);
    }

    int ans = f(target);

    if(ans == INF)
        cout << -1;
    else
        cout << ans;

}

## LCS 最長共同子序列
假設有兩個序列：

序列 A 長度為 m，表示為 A = a1, a2, ..., am
序列 B 長度為 n，表示為 B = b1, b2, ..., bn
我們定義一個二維 DP 陣列 dp[i][j]，表示 A 的前 i 個字符和 B 的前 j 個字符的最長公共子序列的長度。

> LCS 的子序列是指可以不連續出現的元素順序，而不要求是連續的子串。

**解法:**
\begin{flalign}
F(i,j ) &= 0, &\text{when i = 0 or j = 0} \\
&= F(i - 1, j - 1) + 1, &\text{when i = j} \\
&= max(\space F(i-1, j), \space F(i, j-1)) &\text{when i} \neq \text{j}
\end{flalign}

**範例**:
"**abc**dkdkdj" 和 "anddnf**abc**" 的 LCS 是 "abc" 長度 3

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
=
vector<vector<int>> dp(1010, vector<int>(1010, -1));
string s1, s2;

// 長度 i 和 長度 j 的 LCS 長度
int f(int i, int j)
{
    if(i <= 0 || j <= 0) return 0;

    if(dp[i][j] != -1)
    {
        return dp[i][j];
    }
    else
    {
        if(s1[i-1] == s2[j-1])
        {
            dp[i][j] = f(i-1, j-1) + 1;
            return dp[i][j];
        }
        else
        {
            dp[i][j] = max(f(i-1, j), f(i, j-1));
            return dp[i][j];
        }
    }
}

int main()
{
    cout.sync_with_stdio(false);
    cin.tie(nullptr);

    while(cin >> s1)
    {
        cin >> s2;
        cout << f(s1.size(), s2.size()) << endl;
    }
}

# 最大子陣列和 MSS

**解法:**
$F(i) = \text{max}(F(i-1) + a_i \space ,\space a_i)$

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

lint n, t;
vector<lint> vec;
lint dp[(int)2e7 + 10] = {0};

lint maxN;

lint f(lint i)
{
    if(i == 1) return vec[0];

    if(dp[i] != (lint)-1e18)
    {
        return dp[i];
    }
    else
    {
        dp[i] = max(f(i-1) + vec[i-1], vec[i-1]);
        maxN = maxN < dp[i] ? dp[i] : maxN ;
        return dp[i];
    }
}
int main()
{   
    cout.sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 0; i < (int)2e7; i++)
    {
        dp[i] = -1e18;
    }

    for (int i = 0; i < n; i++)
    {
        cin >> t;
        vec.emplace_back(t);
    }

    maxN = vec[0];

    f(n);
    cout << maxN;
}