# Chữa bài DP 16/06/2023

# Cài đặt
## DP bottom-up vs top-down
- Có 2 kiểu cài đặt DP, một kiểu là như sáng nay anh đã chữa cho các bạn, đi từ base case đi lên, gọi là bottom-up.
- Một kiểu nữa gọi là top-down, đi từ trạng thái đáp án đi xuống, để cho dễ hiểu các bạn có thể xem ví dụ code top-down của bài 1:

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define mod 1000000007
 
const int maxn = 1e5 + 5;
 
int dp[maxn];
 
int f(int i){
    // Base case
    if(i == 0 || i == 1) return 1;
    if(i == 2) return 2;
 
     // Trạng thái đã tính rồi thì trả lại kết quả luôn
    if(dp[i] != -1) return dp[i];
 
     // Ốp thẳng công thức vào
    dp[i] = (f(i - 1) + f(i - 2) + f(i - 3)) % mod;
 
    return dp[i];
}
 
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    int n;
    cin >> n;
    
    // Đánh dấu tất cả là chưa tính
    memset(dp, -1, sizeof dp);
    
    // Đi từ trạng thái đáp án đi xuống
    cout << f(n);
}

- Nhìn chung là code kiểu này được cái là phần công thức mình áp dụng vào khác rõ ràng, dễ hiểu. Nhược điểm là đệ quy nên chạy chậm hơn và tốn mem hơn. Nếu mà thuật chuẩn thì code kiểu nào cũng được, các bạn có thể tùy ý mà chọn cách code hợp với mình. Code mẫu các bài ở dưới có theo cả 2 kiểu cho các bạn tham khảo.

## `memset`
- `memset` dùng để fill mảng với một giá trị nào đấy, rất tiện cho các bài toán dp, có thể memset một số giá trị sau:
+ `memset(a, 0, sizeof a)` set toàn bộ mảng a về $0$.
+ `memset(a, 0x3f, sizeof a)` set toàn bộ mảng a về một giá trị rất lớn, coi như dương vô cùng. Nó là `0x3f3f3f3f` với 32-bit và `0x3f3f3f3f3f3f3f3f` với với 64-bit
+ `memset(a,-0x3f, sizeof a)` set toàn bộ mảng a về một giá trị rất nhỏ, coi như âm vô cùng. Tương tự trên.
+ `memset(a, -1, sizeof a)` set toàn bộ mảng a về $-1$.
- Các giá trị khác các bạn for để set hoặc dùng fill, dùng memset là không đúng đâu.

**Lúc sáng chữa bài 2 anh bảo các bạn memset mảng dp về âm vô cùng để gán vào một số trạng thái không tồn tại kiểu "chưa xét đến món đồ nào, cân nặng là 1". Bài này có thể không nhất thiết phải làm vậy, nhưng có một số bài nếu không làm vậy thì sai, nói trước cho các bạn lưu ý trường hợp này.**

## Một số thứ linh tinh khác
- Cập nhật max cho trạng thái dp:
Bình thường các bạn phải làm `dp[i] = max(dp[i], dp[j])` chẳng hạn:

inline void maxi(int &a, int b){
    a = max(a, b);
}

Thì có thể dùng hàm này, chỉ cần viết `maxi(dp[i], dp[j])` code ngắn hơn và dễ đọc hơn.
- Cập nhật tổng cho trạng thái dp:
Bình thường các bạn làm `dp[i] = (dp[i] + dp[j]) % mod`.

inline void add(int &a, int b){
    if((a += b) >= mod) a -= b;
}

Thì giờ chỉ cần dùng `add(dp[i], dp[j])`. Phép trừ sẽ chạy nhanh hơn phép mod, chỉ đúng khi cả `dp[i]` và `dp[j]` nhỏ hơn mod.

Mấy phép toán khác cũng tương tự nhé.

## Bài 1: [Đền Hakurei](https://marisaoj.com/problem/140)
- Trạng thái quy hoạch động $f(i)$ là số cách để đến được bậc thứ $i$. Trạng thái bắt đầu $f(0)=1$.
- Công thức truy hồi là $f(i) = f(i - 1) + f(i - 2) + f(i - 3)$ tương ứng với việc đi $1,2$ hoặc $3$ bậc.

Code:
:::spoiler

#include <bits/stdc++.h>
using namespace std;

#define int long long
 
const int maxn = 1e5 + 5;
 
int n;
int dp[maxn];
 
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    cin >> n;
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
 
    for(int i = 3; i <= n; i++){
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod;
    }
 
    cout << dp[n];
}

:::

## Bài 2: [Cái túi 2](https://marisaoj.com/problem/141)
- Trạng thái quy hoạch động $f(i,j)$, giá trị lớn nhất sau khi đã xét xong món đồ thứ $i$ và tổng cân nặng các vật đã lấy là $j$.
- Công thức truy hồi:
+ $f(i,j)= max \begin{cases}
f(i - 1,j) \text{ trong trường hợp bỏ vật } i\\
f(i - 1,j-w_i) + v_i \text{ trong trường hợp lấy vật } i
\end{cases}$

Code:
:::spoiler

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n, S;
    cin >> n >> S;
 
    vector<int> w(n+1), v(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
 
    vector<vector<int>> dp(n+1, vector<int>(S+1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= S; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
 
    cout << dp[n][S] << endl;
 
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define inf64 0x3f3f3f3f3f3f3f3f
#define int long long

const int maxn = 1e2 + 2;
const int maxs = 1e5 + 5;;

int dp[maxn][maxs];
int v[maxn], w[maxn];

inline void maxi(int &a, int b){
    a = max(a, b);
}

int f(int i, int j){
    if(!i){
        if(!j) return 0;
        return -inf64;
    }

    if(dp[i][j] != -1) return dp[i][j];

    maxi(dp[i][j], f(i - 1, j));
    if(j >= w[i])
        maxi(dp[i][j], f(i - 1, j - w[i]) + v[i]);

    return dp[i][j];
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, S;
    cin >> n >> S;
    for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];
    memset(dp, -1, sizeof dp);

    int ans = 0;
    
    for(int i = 0; i <= S; i++)
        maxi(ans, f(n, i));

    cout << ans;
}

:::

## Bài 3: [Đường đi lớn nhất 2](https://marisaoj.com/problem/142)
- Trạng thái quy hoạch động $f(i,j)$ là đi đến hàng thứ $i$, cột $j$ thì lấy được tối đa bao nhiêu cây nấm.
- Do ô $(i,j)$ chỉ đến được từ $(i-1,j)$ và $(i,j-1)$ nên có công thức truy hồi sau:
+ $f(i,j) = max(f(i-1,j),f(i,j-1)) + a(i,j)$.
- Đáp án là $f(n,n)$.

Code:
:::spoiler

#include <bits/stdc++.h>
using namespace std;

#define int long long
 
const int maxn = 1e3 + 5;
 
int n;
int a[maxn][maxn];
int dp[maxn][maxn];
 
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> a[i][j];
        }
    }
 
    for(int i = 1; i <= n; i++){
        for(int j = 1; j  <= n; j++){
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
        }
    }
 
    cout << dp[n][n];
}

#include <bits/stdc++.h>
using namespace std;

#define inf64 0x3f3f3f3f3f3f3f3f
#define int long long

const int maxn = 1e3 + 2;

int dp[maxn][maxn];
int a[maxn][maxn];
int n;

inline void maxi(int &a, int b){
    a = max(a, b);
}

int f(int i, int j){
    if(!i || !j) return 0;

    if(dp[i][j] != -1) return dp[i][j];

    maxi(dp[i][j], max(f(i - 1,j), f(i, j - 1)) + a[i][j]);

    return dp[i][j];
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];

    memset(dp, -1, sizeof dp);
    cout << f(n, n);
}

:::

## Bài 4: [Dãy con tăng dài nhất](https://marisaoj.com/problem/143)
- Trạng thái quy hoạch động $f(i)$ là độ dài của LIS kết thúc ở vị trí $i$.
- Công thức truy hồi $f(i) = max(f(j) + 1)$ với $j < i$ và $a_j < a_i$.
- Đáp án là $f(n,n)$.

Code:
:::spoiler

#include<bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> A(n), dp(n, 1);
    for(int i = 0; i < n; i++) {
        cin >> A[i];
    }
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(A[j] < A[i]) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
    }
    int ans = 1;
    for(int i = 0; i < n; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define inf64 0x3f3f3f3f3f3f3f3f
#define int long long

const int maxn = 1e3 + 2;

int dp[maxn];
int a[maxn];
int n;

inline void maxi(int &a, int b){
    a = max(a, b);
}

int f(int i){
    if(dp[i] != -1) return dp[i];
    dp[i] = 1;

    for(int j = 1; j <= i - 1; j++){
        if(a[j] < a[i])
            maxi(dp[i], f(j) + 1);
    }
    return dp[i];
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];

    memset(dp, -1, sizeof dp);
    
    int ans = 0;
    for(int i = 1; i <= n; i++){
        maxi(ans, f(i));
    }
    cout << ans;
}

:::

## Bài 5: [Dãy con chung dài nhất](https://marisaoj.com/problem/144)
- Trạng thái quy hoạch động $f(i,j)$ là độ dài LCS khi xét hết $i$ phần tử đầu của $A$ và $j$ phần tử đầu của $B$.
- Công thức truy hồi:
+ $f(i,j)= max \begin{cases}
f(i - 1,j) \text{ trong trường hợp bỏ } A_i\\
f(i,j-1)\text{ trong trường hợp bỏ } B_j\\
f(i-1,j-1) + 1 \text{ trong trường hợp } A_i=B_j, \text{kết nạp chúng vào } LCS
\end{cases}$

:::spoiler

#include <bits/stdc++.h>
using namespace std;
 
#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end())
#define int long long
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"
 
const int maxn = 1e3 + 5;
 
int n;
int a[maxn];
int b[maxn];
int dp[maxn][maxn];
 
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
 
    for(int i = 1; i <= n; i++){
        cin >> b[i];
    }
 
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            //Skip thang i
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
 
            //SKip thang j
            dp[i][j] = max(dp[i][j], dp[i][j - 1]);
 
            //a[i] = b[j] tang dap an
            if(a[i] == b[j]){
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
    }
 
    cout << dp[n][n];
}

#include <bits/stdc++.h>
using namespace std;

#define inf64 0x3f3f3f3f3f3f3f3f
#define int long long

const int maxn = 1e3 + 2;

int dp[maxn][maxn];
int a[maxn], b[maxn];
int n;

inline void maxi(int &a, int b){
    a = max(a, b);
}

int f(int i, int j){
    if(!i || !j) return 0;

    if(dp[i][j] != -1) return dp[i][j];

    maxi(dp[i][j], max(f(i - 1, j), f(i, j - 1)));

    if(a[i] == b[j]){
        maxi(dp[i][j], f(i - 1, j - 1) + 1);
    }

    return dp[i][j];
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    
    for(int i = 1; i <= n; i++)
        cin >> b[i];

    memset(dp, -1, sizeof dp);
    
    cout << f(n, n);
}

:::

# Gợi ý một số bài

## Bài 6: [Ghen tuông](https://marisaoj.com/problem/160)
- Trạng thái
:::spoiler
$f(i,j,k)$ là niềm vui tối đa sau khi hết ngày $i$, đi chơi với người $j$ ở ngày $i$, và đã đi chơi với người $j$ $k$ ngày liên tiếp.
:::

## Bài 7: [Đồng xu](https://marisaoj.com/problem/151)
- Trạng thái
:::spoiler
$f(i)$ là số lượng đồng xu ít nhất để có được số tiền $i$.
:::

## Bài 8: [Đồng xu 2](https://marisaoj.com/problem/158)
- Trạng thái
:::spoiler
$f(i,j)$ là số lượng cách chọn $j$ tiền khi xét hết $i$ loại xu đầu tiên. Chú ý là có tính thứ tự nên các bạn phải lần lượt xét các đồng xu trước.

Có $10^8$ trạng thái nên không thể làm mảng $n \times k$ được, thay vào đó các bạn có thể bỏ chiều $i$ đi.
:::