# week1-simple dp

## 經典 DP 例題

### Knapsack Problem 背包問題

給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高？

定義 $dp[i][j]$ 為看到第 $i$ 個貨物時有 $j$ 的空間被占據時的最大利潤。

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define io_o() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fst first
#define scd second
#define endl "\n"
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define REP(i,n) for(int i = 0; i < n; i++)
#define print1d(a) {for(auto v: a) cout << v << " "; cout << endl;}
#define int ll

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int32_t main(){
    io_o();
    int n;
    while(cin >> n) {
        vector<vi> dp(n + 1, vi(101));
        int ans = 0;
        REP(i, n) {
            int v, c; cin >> v >> c;
            REP(j, 101) {
                dp[i + 1][j] = dp[i][j];
                if(j + v <= 100)
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j + v] + c);
                ans = max(ans, dp[i + 1][j]);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

[https://zerojudge.tw/ShowProblem?problemid=b184](https://zerojudge.tw/ShowProblem?problemid=b184)

### Longest Common Subsequence(LCS) 問題

定義 $dp[i][j]$ 為 text1 的前 $i$ 個字符和 text2 的前 $j$ 個字符的 LCS 長度。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }
};

[https://leetcode.com/problems/longest-common-subsequence/description/](https://leetcode.com/problems/longest-common-subsequence/description/)

## 個人練習

### 做題規則

1. 限時 5 小時，提早寫完即可提早交卷，沒 AC 所有題目不可提早交卷。
2. 不可以看此文件和 C++ docs 以外的文件。
3. 不會的題目在答題完成之後搞懂，會的題目也需要説明想法，因爲有些題目具備多種解法，仍需確認你有辦法用 dp 寫出此題。
4. 未按照題目難度排序，請盡量寫出更多的題目。
5. uva1626 請不要提交到 judge，我有改過輸出需求。

### 題目

#### uva1626

簡化題目：只需要輸出需要加入多少字符即可。

https://vjudge.net/problem/UVA-1626/origin

#### cses1633

https://vjudge.net/problem/CSES-1633/origin

#### uva11450

https://vjudge.net/problem/UVA-11450/origin

#### cf1447d

https://vjudge.net/problem/CodeForces-1447D/origin

#### cf180c

https://vjudge.net/problem/CodeForces-180C/origin

#### cf1027e

https://vjudge.net/problem/CodeForces-1027E/origin

#### cf540d

https://vjudge.net/problem/CodeForces-540D/origin