---
title:
Quy hoạch động (Phần 1: Quy hoạch động cơ bản)
---

Quy hoạch động (Phần 1: Quy hoạch động cơ bản)
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Kiến thức cần có
Để hiểu hơn về kĩ thuật **Quy hoạch động**, trước hết bạn hãy tìm hiểu:
- Kĩ thuật [Đệ quy và quay lui](https://hackmd.io/zq12mu3IScqbYy9a9HtSRw?view)

# Khái niệm

- Cùng trở về bài toán tính số Fibonacci thứ $n$, ta đã biết được cách tính trong $O(2^n)$ bằng kĩ thuật Đệ quy:

int f(int n) {
    if (n == 1) return 0; // trường hợp cơ sở 1
    if (n == 2) return 1; // trường hợp cơ sở 2
    return f(n - 1) + f(n - 2); // phần đệ quy
}
// Xem lại bài viết về kĩ thuật Đệ quy và quay lui để hiểu rõ hơn

- Tuy nhiên, cách này không hiệu quả trong trường hợp $n$ của đề bài lớn, hoặc ta cần tính nhiều số Fibonacci. Ví dụ: In số Fibonacci từ $1$ đến $n$ $(n \le 40)$.
- Ta nhận thấy một trạng thái có thể phải tính lại nhiều lần:
- $f(5)$ gọi xuống $f(4)$ và $f(3)$.
- $f(4)$ gọi xuống $f(3)$ và $f(2)$.
- $f(3)$ trong hàm đệ quy tính lại $2$ lần khiến thời gian chương trình chạy rất lâu.

- Để tránh việc phải tính lại một trạng thái nhiều lần, ta có thể lưu trữ trạng thái đó để sử dụng trong những lần tính sau, từ đó ta có chương trình được cải tiến:

#include <bits/stdc++.h>

using namespace std;

int fib[41]; // mảng lưu lại fib[i]

int f(int n)
{
    if (fib[n]!=-1) return fib[n];
    fib[n] = f(n - 1) + f(n - 2);
    return fib[n];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i) fib[i] = -1; 
    // Định nghĩa fib[i] = -1 là fib[i] chưa được tính
    fib[1] = 0;
    fib[2] = 1;
    for(int i = 1; i <= n; ++i) cout << f(i) << endl;
}

> So sánh thời gian chạy chương trình sau khi thêm mảng fib với thời gian chạy chương trình nếu ta sử dụng hàm đệ quy ban đầu.

- Bằng cách lưu lại giá trị của những số fibonacci đã được tính trước đó, ta tối ưu được thời gian xử lí của chương trình. Kĩ thuật này được gọi là Quy hoạch động.
- Kĩ thuật này thường được sử dụng để giải quyết các bài toán đếm, các bài toán tìm hướng giải tối ưu.

::: spoiler **Bonus**
::: info
- Ngoài cách cài bằng hàm đệ quy, ta còn có thể cài đặt bài toán trên bằng vòng lặp.
- Cách 2:

#include <bits/stdc++.h>

using namespace std;

int fib[41]; // mảng lưu lại fib[i]

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    fib[1] = 0;
    fib[2] = 1;
    for(int i = 3; i <= n; ++i) fib[i] = fib[i - 1] + fib[i - 2];
    for(int i = 1; i <= n; ++i) cout << fib[i] << endl;
}

- Cách 3:

#include <bits/stdc++.h>

using namespace std;

int fib[41]; // mảng lưu lại fib[i]

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    fib[1] = 0;
    fib[2] = 1;
    for(int i = 1; i <= n - 1; ++i)
    {
        if(i + 1 <= n) fib[i + 1] += fib[i];
        if(i + 2 <= n) fib[i + 2] += fib[i];
    }
    for(int i = 1; i <= n; ++i) cout << fib[i] << endl;
}

- Cả hai cách này sẽ được đề cập trong phần sau của bài viết.
:::

## Trạng thái bài toán

- **Trạng thái** là một trường hợp, hay một kết quả của **bài toán con** của bài toán ta đang giải quyết.
- Ví dụ:
- Gọi $fib_i$ là số fibonacci thứ $i$, khi đó $fib_i$ là một trạng thái.
- Gọi $p_i$ là tổng các phần tử từ $1$ đến $i$ của mảng, $p_i$ cũng là một trạng thái.
- Gọi $dp_{i,j}$ là số cách tạo số tự nhiên gồm $i$ chữ số, chỉ sử dụng các chữ số từ $1$ đến $j$, $dp_{i,j}$ cũng chính là một trạng thái
- Kết quả của bài toán ta cần giải quyết sẽ được tính từ các trạng thái dựa trên mối liên hệ của chúng, và được thể hiện bằng **công thức truy hồi**.

## Công thức truy hồi

### Khái niệm

- **Công thức truy hồi** là công thức tính **một trạng thái** bất kì của một dãy số bằng **những trạng thái khác** trong dãy số đó.
- Ví dụ:
- $f_i = f_{i-1} \cdot 2$ là một công thức truy hồi.
- $f_i = 5$ không phải là một công thức truy hồi (Do $f_i$ không được tính từ một trạng thái nào khác của $f$).
- $f_i = f_{i+1} + a_i$ (Công thức suffix sum) cũng là một công thức truy hồi.

### Trường hợp cơ sở
* **Trường hợp cơ sở** là **trạng thái** bắt đầu của một dãy số được tính bằng **công thức truy hồi**.
* Ví dụ:
- Dãy Fibonacci có công thức truy hồi là: $f_i = f_{i - 1} + f_{i - 2}$, có trường hợp cơ sở là $f_1 = 0$ và $f_2 = 1$
- Dãy prefix sum có công thức truy hồi là: $f_i = f_{i - 1} + a_i$, có trường hợp cơ sở là $f_0 = 0$
### Cách biểu diễn công thức truy hồi trong bài toán

- Công thức truy hồi có thể được biểu diễn theo 2 cách:
- **Đẩy trạng thái**: Cập nhật các trạng thái sau dựa trên trạng thái hiện tại
- **Kéo trạng thái**: Tính toán trạng thái hiện tại dựa trên các trạng thái trước đó

- Cùng xét lại công thức tính số Fibonacci:

#### Đẩy trạng thái

- Từ trạng thái $fib_i$, ta có thể cập nhật cho trạng thái $fib_{i+1}$ và $fib_{i+2}$ vì hai trạng thái này được tính qua trạng thái $fib_i$.
- $fib_0 = 1, fib_1 = 2$.
- $fib_{i+1} += fib_i, \forall i$.
- $fib_{i+2} += fib_i, \forall i$.
::: spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

int fib[41]; // mảng lưu lại fib[i]

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    fib[1] = 0;
    fib[2] = 1;
    for(int i = 1; i <= n - 1; ++i)
    {
        if(i + 1 <= n) fib[i + 1] += fib[i];
        if(i + 2 <= n) fib[i + 2] += fib[i];
    }
    for(int i = 1; i <= n; ++i) cout << fib[i] << endl;
}

:::

#### Kéo trạng thái

- Trạng thái $fib_i$ được tính từ hai trạng thái trước đó là $fib_{i-1}$ và $fib_{i-2}$.
- $fib_0 = 1, fib_1 = 2$.
- $fib_i = fib_{i-1} + fib_{i-2}, \forall i \ge 3$.

::: spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

int fib[41]; // mảng lưu lại fib[i]

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    fib[1] = 0;
    fib[2] = 1;
    for(int i = 3; i <= n; ++i) fib[i] = fib[i - 1] + fib[i - 2];
    for(int i = 1; i <= n; ++i) cout << fib[i] << endl;
}

:::

- Mỗi cách biểu diễn đều có ưu điểm, khuyết điểm riêng. Tuy nhiên, nhìn chung hai cách biểu diễn là **tương đương** nhau. Tùy thuộc bài toán hoặc cảm nhận của mỗi người mà có thể chọn cách biểu diễn cho riêng mình.

## Một số ví dụ điển hình
### Bài toán 1: [Frog 1](https://oj.vnoi.info/problem/atcoder_dp_a)
#### Đề bài:
* Có $N$ hòn đá, được đánh số từ 1 đến $N$. Với mỗi chỉ số $i$ $(1 \le i \le N)$, độ cao của hòn đá thứ $i$ là $h_i$
* Ban đầu, có một chú ếch đang ngồi ở hòn đá thứ nhất và chú sẽ thực hiện liên tục một loạt các hành động sau:
- Nếu chú đang ngồi ở hòn đá $i$, chú có thể nhảy đến hòn đá thứ $i + 1$ hoặc $i + 2$. Chú sẽ mất chi phí khi nhảy là $|h_i - h_j|$ với $j$ là hòn đá mà chú ếch nhảy đến.
* Bạn hãy giúp chú ếch tìm chi phí tối thiểu để nhảy từ hòn đá thứ nhất đến hòn đá thứ $N$ nhé.
#### Input:
* Dòng đầu tiên của dữ liệu vào chứ số nguyên dương $N$ $(2 \le N \le 10^5)$, là số lượng hòn đá.
* Dòng thứ hai gồm $N$ số nguyên $h_i$ $(1 \le i \le N, 1 \le h_i \le 10^4)$, là độ cao của hòn đá thứ $i$.
#### Output:
* Gồm một số nguyên, là chi phí ít nhất để nhảy từ hòn đá thứ nhất đến hòn đá thứ $N$.
#### Sample Input:

4
10 30 40 20

#### Sample Output:

30

Giải thích: Một đường đi tối ưu là: $1 → 2 → 4$. Chi phí sẽ là $|10 - 30| + |30 - 20| = 30$
### Lời giải:
::: spoiler **Ý tưởng:**
* Ta gọi $dp[i]$ là chi phí tối thiếu để chú ếch nhảy từ hòn đá thứ nhất đến hòn đá thứ $i$.
* Ta thấy rằng $dp[i]$ sẽ được tính bởi 2 trạng thái:
- Chú ếch nhảy từ hòn đá thứ $i - 1$ đến hòn đá thứ $i$: $dp[i] = dp[i - 1] + |h[i] - h[i - 1]|$
- Chú ếch nhảy từ hòn đá thứ $i - 2$ đến hòn đá thứ $i$: $dp[i] = dp[i - 2] + |h[i] - h[i - 2]|$
- min của 2 giá trị trên sẽ là đáp án của $dp[i]$.
* Trường hợp cơ sở của bài toán này sẽ là:
- $dp[1] = 0$ vì ngay từ đầu chú ếch đã ở ô thứ nhất.
- $dp[2] = |h[2] - h[1]|$ vì chú ếch chỉ có thể nhảy từ ô $1$ đến ô $2$
:::
::: spoiler **Cài đặt:**

#include <bits/stdc++.h>

using namespace std;

int h[100005], n;
long long dp[100005];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> h[i];
    dp[1] = 0;
    dp[2] = abs(h[2] - h[1]); 
    for (int i = 3; i <= n; i++)
    {
        dp[i] = min(abs(h[i] - h[i - 1]) + dp[i - 1], abs(h[i] - h[i - 2]) + dp[i - 2]);
    }
    cout << dp[n];
    return 0;
}

:::
### Bài toán 2: [NKTICK](https://oj.vnoi.info/problem/nktick)
* Có $N$ người sắp hàng mua vé dự buổi hoà nhạc. Ta đánh số họ từ $1$ đến $N$ theo thứ tự đứng trong hàng. Mỗi người cần mua một vé, song người bán vé được phép bán cho mỗi người tối đa hai vé. Vì thế, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết $t_i$ là thời gian cần thiết để người $i$ mua xong vé cho mình. Nếu người $i + 1$ rời khỏi hàng và nhờ người $i$ mua hộ vé thì thời gian để người thứ $i$ mua được vé cho cả hai người là $r_i$.
* **Yêu cầu:** Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất.
#### Input:
* Dòng đầu tiên chứa số $N$ $(1 \le N \le 60000)$.
* Dòng thứ 2 ghi N số nguyên dương $t_1, t_2, ..., t_N$. $(1 \le t_i \le 30000)$
* Dòng thứ ba ghi N-1 số nguyên dương $r_1, r_2, ..., r_{N-1}$. $(1 \le r_i \le 30000)$
#### Output:
* In ra tổng thời gian phục vụ nhỏ nhất.
#### Sample Input:

5
2 5 7 8 4
4 9 10 10 

#### Sample Output:

18

### Lời giải:
::: spoiler **Ý tưởng:**
* Ta gọi $dp[i]$ là tổng thời gian phục vụ nhỏ nhất cho $i$ người đầu tiên.
* Ta thấy rằng $dp[i]$ sẽ được tính bởi 2 trạng thái:
- Người thứ $i$ tự mua vé: $dp[i - 1] + t[i]$.
- Người thứ $i$ nhờ người thứ $i - 1$ mua vé cho cả hai: $dp[i - 2] + r[i - 1]$
- min của 2 giá trị trên sẽ là đáp án của $dp[i]$.
* Trường hợp cơ sở của bài toán này sẽ là:
- $dp[0] = 0$ vì ban đầu không có ai cần mua vé.
- $dp[1] = t[1]$ vì nếu chỉ có người đầu tiên thì người ấy chỉ có thể tự mua cho chính mình.
:::
::: spoiler **Cài đặt:**

#include <bits/stdc++.h>  

using namespace std;

const int N = 2e5 + 5;

int n, t[N], r[N]; 
long long dp[N];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> t[i];
    for (int i = 1; i <= n; ++i) cin >> r[i];
    dp[0] = 0;
    dp[1] = t[1];
    for (int i = 2; i <= n; ++i)
    {
        dp[i] = min(dp[i - 1] + t[i], dp[i - 2] + r[i - 1]);
    }
    cout << dp[n];
    return 0;
}

:::
# Phương pháp tiếp cận bài toán Quy hoạch động

- Sau khi tìm hiểu các khái niệm ta cần biết khi nào có thể sử dụng phương pháp quy hoạch động và làm thế nào để tìm ra công thức truy hồi.
- Quy hoạch động dựa trên ý tưởng chia bài toán ban đầu thành bài toán nhỏ hơn có tính chất tương tự. Khi bài toán nhỏ đến mức độ ta có thể tự tính được trạng thái ban đầu, ta áp dụng công thức truy hồi để tìm ra kết quả cuối cùng
- Để hiểu rõ hơn, ta cùng thử giải [Free Contest 98 - REWARD](https://oj.vnoi.info/problem/fc098_reward).

#### Đề bài

- Vì vừa đạt giải cao trong một kì thi nên bạn Quý được ban tổ chức trao thưởng. Thể lệ trao thưởng như sau:
- Có $N$ bàn xếp thành một hàng ngang, trên mỗi bàn chứa một món quà.
- Bạn Quý được chọn bất kì món quà nào, hoặc không chọn, nhưng không được chọn quá 2 món quà liên tiếp.
- Bạn hãy giúp bạn Quý tính xem có thể chọn lượng quà có giá trị lớn nhất là bao nhiêu.

#### Input

- Dòng đầu ghi một số nguyên $N$.
- Dòng thứ hai ghi $N$ số nguyên $A_1, A_2, ..., A_N$ thể hiện giá trị của $N$ món quà.

#### Output

- In ra tổng giá trị các món quà lớn nhất mà bạn Quý có thể chọn.

#### Sample Input

5 
6 9 1 3 5

#### Sample Output

23

#### Giới hạn

- 40% số test có $1 \le N \le 20$.
- 60% số test còn lại có $1 \le N \le 10^5$.
- $0 \le |Ai| \le 10^6$.

#### Giải thích

- Dãy được chọn là $6, 9, 3, 5$

## Subtask 40%

- Mọi bài toán quy hoạch động đều xuất phát từ thuật toán ngây thơ, tức là nói gì làm đó.
- Vì $n \le 20$, ta có thể quay lui thử hết tất cả tập con có thể và chọn tập con lớn nhất
- Tại mỗi vị trí $i$ đang xét, ta có $3$ trường hợp có thể xảy ra
- Trường hợp 1: Chưa chọn phần tử nào ngay trước đó. Ta có thể chọn lấy hoặc không lấy $a_i$.
- Trường hợp 2: Trước đó đã chọn $1$ phần tử. Ta cũng có thể chọn lấy hoặc không lấy $a_i$.
- Trường hợp 3: Trước đó đã chọn $2$ phần tử. Ta chỉ có thể bỏ qua $a_i$.
::: spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

int n;
int a[100005];

long long waylouis(int idx, long long sum, int chosen)
{
    if(idx == n + 1) return sum;
    if(chosen == 2) return waylouis(idx + 1, sum, 0);
    else if(chosen == 1) return max(waylouis(idx + 1, sum, 0), waylouis(idx + 1, sum + a[idx], 2));
    else return max(waylouis(idx + 1, sum, 0), waylouis(idx + 1, sum + a[idx], 1));
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    cout << waylouis(1, 0, 0) << endl;
}

:::

- Độ phức tạp của cách này là $O(2^n)$, không đủ nhanh cho subtask sau. Lúc này ta nghĩ đến tối ưu bằng Quy hoạch động.

## Gọi trạng thái Quy hoạch động

- Dựa trên thuật toán quay lui, ta có $n$ phần tử và $3$ trường hợp ở mỗi phần tử. Ta gọi $dp_{i,j}$ là tập con thỏa mãn yêu cầu bài toán tối ưu khi xét đến $i$ phần tử đầu tiên, trường hợp hiện tại là $j$ ($j$ chứa các giá trị $\in {0, 1, 2}$, ứng với số phần tử đã chọn khi xét $i$).

## Xác định kết quả cuối cùng của bài toán

- Ta cần thử hết cả $3$ trường hợp của phần tử cuối cùng, kết quả cuối cùng là $max(dp_{n,0},dp_{n,1},dp_{n,2})$.

## Xác định trường hợp cơ sở và công thức truy hồi

> Phần này bài viết sẽ trình bày công thức truy hồi theo cách kéo trạng thái.
- Ban đầu ta không có gì trong tập: $dp_{0,0} = 0$.
- Trường hợp $0$: Ta không chọn phần tử nào: $dp_{i,0} = max(dp_{i-1,0},dp_{i-1,1},dp_{i-1,2})$.
- Trường hợp $1$: Ta chọn phần tử $i$: $dp_{i,1} = dp_{i-1,0} + a_i$.
- Trường hợp $2$: Ta chọn phần tử $i$ và phần tử trước đó: $dp_{i,2} = dp_{i-1,1} + a_i$.

## Cài đặt bài toán

- Việc cuối cùng ta cần làm đó chính là biến công thức truy hồi thành chương trình. Phần này nhường lại cho bạn đọc.
- Tuy nhiên, nếu cần thì có thể tham khảo
::: spoiler Cài đặt

#include <bits/stdc++.h>

using namespace std;

int n;
int a[100005], dp[100005][3];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    dp[0][0] = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(i == 1)
        {
            dp[i][0] = 0;
            dp[i][1] = dp[i - 1][0] + a[i];
            // Có tối đa 1 phần tử -> chọn được 2 phần tử là vô lí nên không tồn tại trường hợp dp[1][2]
        }
        else
        {
            dp[i][0] = max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
            dp[i][1] = dp[i - 1][0] + a[i];
            dp[i][2] = dp[i - 1][1] + a[i];
        }
    }
    cout << max({dp[n][0], dp[n][1], dp[n][2]});
}

:::

# Bài tập

## [Atcoder Educational DP Contest B - Frog 2](https://oj.vnoi.info/problem/atcoder_dp_b)

#### Đề bài
* Có $N$ hòn đá, được đánh số từ $1$ đến $N$. Với mỗi chỉ số $i$ $(1 \le i \le N)$, độ cao của hòn đá thứ $i$ là $h_i$
* Ban đầu, có một chú ếch đang ngồi ở hòn đá thứ nhất và chú sẽ thực hiện liên tục một loạt các hành động sau:
- Nếu chú đang ngồi ở hòn đá $i$, chú có thể nhảy đến các hòn đá thứ $i + 1, i + 2...i + K$. Chú sẽ mất phí khi nhảy là $|h_i - h_j|$ với $j$ là hòn đá mà chú ếch nhảy đến.
* Bạn hãy giúp chú ếch tìm chi phí tối thiểu để nhảy từ hòn đá thứ nhất đến hòn đá thứ $N$ nhé.
#### Input
* Dòng đầu tiên của dữ liệu vào chứa hai số nguyên dương $N$ và $K$ $(2 \le N \le 10^5, 1 \le K \le 100)$, lần lượt là số lượng hòn đá và giới hạn nhảy của ếch.
* Dòng thứ hai gồm $N$ số nguyên $h_i$ $(1 \le i \le N, 1 \le h_i \le 10^4)$, là độ cao của hòn đá thứ $i$.
#### Output
* Gồm một số nguyên, là chi phí ít nhất để nhảy từ hòn đá thứ nhất đến hòn đá thứ $N$.
#### Sample Input

5 3
10 30 40 50 20

#### Sample Output

30

#### Giải thích
* Một đường đi tối ưu là: $1 → 2 → 5$. Chi phí sẽ là $|10 - 30| + |30 - 20| = 30$
#### Lời giải
:::spoiler **Ý tưởng**
* Ta gọi $dp[i]$ là chi phí tối thiếu để chú ếch nhảy từ hòn đá thứ nhất đến hòn đá thứ $i$.
* Ta thấy rằng $dp[i]$ sẽ được tính bởi $K$ trạng thái:
- Chú ếch nhảy từ hòn đá thứ $i - 1$ đến hòn đá thứ $i$: $dp[i] = dp[i - 1] + |h[i] - h[i - 1]|$
- Chú ếch nhảy từ hòn đá thứ $i - 2$ đến hòn đá thứ $i$: $dp[i] = dp[i - 2] + |h[i] - h[i - 2]|$
- ...
- Chú ếch nhảy từ hòn đá thứ $i - K$ đến hòn đá thứ $i$: $dp[i] = dp[i - K] + |h[i] - h[i - K]|$
- min của $K$ giá trị này sẽ là $dp[i]$.
* Trường hợp cơ sở của bài toán này sẽ là:
- $dp[1] = 0$ vì ngay từ đầu chú ếch đã ở ô thứ nhất.
- $dp[2] = |h[2] - h[1]|$ vì chú ếch chỉ có thể nhảy từ ô $1$ đến ô $2$
:::
:::spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

int n, k, dp[100005], h[100005];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> h[i]; 
    dp[1] = 0;
    dp[2] = abs(h[2] - h[1]);
    for (int i = 3; i <= n; ++i)
    {
        int cur = INT_MAX;
        for (int j = 1; j <= k; ++j)
        {
            if (i - j < 1) break;
            cur = min(cur, dp[i - j] + abs(h[i] - h[i - j]));
        }
        dp[i] += cur;
    }
    cout << dp[n];
}

:::
## [Atcoder Educational DP Contest C - Vacation](https://oj.vnoi.info/problem/atcoder_dp_c)

#### Đề bài
* Kỳ nghỉ hè của Taro bắt đầu vào ngày mai, nên anh ấy đã quyết định lên kế hoạch cho nó ngay bây giờ.
* Kỳ nghỉ bao gồm $N$ ngày. Vào ngày thứ $i$ $(1 \le i \le N)$, Taro sẽ chọn và tham gia một trong các hoạt động sau:
- A: Bơi ở biển - nhận được $a_i$ điểm hạnh phúc.
- B: Bắt bọ trên núi - nhận được $b_i$ điểm hạnh phúc.
- C: Làm bài tập ở nhà - nhận được $c_i$ điểm hạnh phúc.
* Vì Taro dễ cảm thấy buồn chán nên anh không thể tham gia các hoạt động giống nhau trong hai ngày liên tiếp trở lên.
* Tìm tổng số điểm hạnh phúc **tối đa** mà Taro có thể nhận được.
#### Input
* Dòng đầu tiên là số nguyên $N$ $(1 \le N \le 10^5)$
* Dòng thứ $i$ trong số $N$ dòng tiếp theo chứa $3$ số nguyên $a_i, b_i, c_i$ $(1 \le a_i, b_i, c_i \le 10^4)$. lần lượt là điêm hạnh phúc có thể nhận được khi Taro tham gia hoạt động $A, B, C$ của ngày thứ $i$.
#### Output
* In ra một số nguyên duy nhất là tổng điểm hạnh phúc tối đa mà Taro có thể nhận được.
#### Sample Input

3
10 40 70
20 50 80
30 60 90

#### Sample Output

210

#### Giải thích
* Nếu Taro tham gia các hoạt động theo thứ tự $C, B, C$, anh ấy sẽ có được $70 + 50 + 90 = 210$ điểm hạnh phúc.
#### Lời giải
:::spoiler **Ý tưởng**
* Ta gọi $dp[i][j]$ là tổng điểm hạnh phúc tối đa mà Taro có thể nhận được sau $i$ ngày và ngày cuối cùng thực hiện hành động $j$ ( Để cho dễ cài đặt ta sẽ dùng chỉ số $1$ tượng trưng $A$, $2$ cho $B$ và $3$ cho $C$ ).
* Ta thấy rằng $dp[i][j]$ sẽ được tính bởi $2$ trạng thái khác $j$ của ngày $i - 1$ vì Taro không hoạt động giống nhau 2 ngày liên tiếp:
* Ví dụ với $j = 1$, $dp[i][j]$ sẽ được tính bằng 2 trạng thái:
- Ngày trước Taro làm hành động $2$: $dp[i - 1][2]$.
- Ngày trước Taro làm hành động $3$: $dp[i - 1][3]$.
- Max của 2 trạng thái này cộng với giá trị $a[i][j]$ (điểm hạnh phúc khi làm hành động $j$ ở ngày $i$) sẽ là giá trị của $dp[i][j]$.
* Với $j = 2$, $j = 3$ ta cũng sẽ có công thức truy hồi tương tự:
- $j = 2$: $dp[i][j] = max(dp[i - 1][1], dp[i - 1][3]) + a[i][j]$ (điểm hạnh phúc khi làm hành động $j$ ở ngày $i$).
- $j = 3$: $dp[i][j] = max(dp[i - 1][1], dp[i - 1][2]) + a[i][j]$ (điểm hạnh phúc khi làm hành động $j$ ở ngày $i$).
* Trường hợp cơ sở của bài toán này sẽ là:
- $dp[0][1] = dp[0][2] = dp[0][3] = 0$ vì nếu chưa bắt đầu làm hành động nào thì số điểm ban đầu của Taro là 0.
:::
:::spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

int n, a[100005][5], dp[100005][5];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= 3; ++j) cin >> a[i][j];
    }
    for (int i = 1; i <= n; ++i)
    {
        dp[i][1] = max(dp[i - 1][2], dp[i - 1][3]) + a[i][1];
        dp[i][2] = max(dp[i - 1][1], dp[i - 1][3]) + a[i][2];
        dp[i][3] = max(dp[i - 1][1], dp[i - 1][2]) + a[i][3];
    }
    cout << max({dp[n][1], dp[n][2], dp[n][3]});
}

:::
## [Đường đi có tổng lớn nhất](https://oj.vnoi.info/problem/qbmax)

#### Đề bài

- Cho một bảng $A$ kích thước $m \times n$, trên đó ghi các số nguyên $a_{ij}$. Một người xuất phát tại ô nào đó của cột $1$, cần sang cột $n$ (tại ô nào cũng được).

- Quy tắc đi: Từ ô $(i, j)$ chỉ được quyền sang một trong $3$ ô $(i, j+1)$; $(i-1, i+1)$; $(i+1, j+1)$.

#### Input

- Dòng $1$: Ghi hai số $m$, $n$ là số hàng và số cột của bảng.
- $m$ dòng tiếp theo, dòng thứ $i$ ghi đủ $n$ số trên hàng $i$ của bảng theo đúng thứ tự từ trái qua phải.

#### Output

- Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được

#### Sample Input

5 7
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7

#### Sample Output

41

#### Giới hạn

- $1 \le m$, $n \le 100$.
- $|a_{ij}| \le 100$.

#### Giải thích

- Bắt đầu từ ô $(1,1)$: Đường đi có tổng lớn nhất gồm các ô $(1,1)$, $(2,2)$, $(3,3)$, $(2,4)$, $(3,5)$, $(4,6)$, $(5,7)$. $9-1+8+7+5+6+7 = 41$.

#### Lời giải
:::spoiler **Ý tưởng**
- Đề bài yêu cầu ta tính đường đi có tổng lớn nhất từ cột $1$ đến cột $n$. Vì thế, tại mỗi ô ta gọi $dp_{i,j}$ là tổng đường đi có tổng lớn nhất từ cột $1$ đến ô $(i,j)$.
- Từ đó suy ra kết quả của bài toán là kết quả của ô lớn nhất trong $m$ ô của cột $n$: $max(dp_{i,n})$, $(1 \le i \le m)$.
- Trường hợp cơ sở: Kết các ô trên cột $1$ là giá trị của ô đó, các ô còn lại đặt là $0$.
- Công thức truy hồi: Ô $(i,j)$ có thể đi đến từ $3$ ô $(i-1,j-1)$, $(i,j-1)$, $(i+1,j-1)$. Từ đó suy ra $dp_{i,j} = max(dp_{i-1,j-1},dp_{i,j-1},dp_{i+1,j-1})+a_{i,j}$.
> Trường hợp $i-1$ hoặc $i+1$ ra ngoài bảng, giá trị của trạng thái đó là $0$.
:::
:::spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

int n, m;
int a[105][105], dp[105][105];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> m >> n;
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            cin >> a[i][j];
            if (j == 1) dp[i][j] = a[i][j];
            else dp[i][j] = 0;
        }
    }
    int ans = -1e9;
    for (int j = 2; j <= n; ++j)
    {
        for (int i = 1; i <= m; ++i)
        {
            if (i == 1) dp[i][j] = max(dp[i][j - 1], dp[i + 1][j - 1]) + a[i][j];
            else if (i == m) dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 1]) + a[i][j];
            else dp[i][j] = max({dp[i - 1][j - 1], dp[i][j - 1],dp[i + 1][j - 1]}) + a[i][j];
            // Lưu ý: Ta chạy vòng lặp j bên ngoài i để đảm bảo mọi trạng thái trước trạng thái hiện tại đã được tính xong
            if (j == n) ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << endl;
}

:::

## [VM 08 Bài 01 - Bậc thang](https://oj.vnoi.info/problem/vsteps)

#### Đề bài
- Bờm chơi trò chơi điện tử Lucky Luke đến màn phải điều khiển Lucky leo lên một cầu thang gồm $N$ bậc.

- Các bậc thang được đánh số từ 1 đến $N$ từ dưới lên trên. Lucky có thể đi lên một bậc thang, hoặc nhảy một bước lên hai bậc thang. Tuy nhiên một số bậc thang đã bị thủng do cũ kỹ và Lucky không thể bước chân lên được. Biết ban đầu, Lucky đứng ở bậc thang số 1 (bậc thang số 1 không bao giờ bị thủng).

- Chơi đến đây, Bờm chợt nảy ra câu hỏi: có bao nhiêu cách để Lucky leo hết được cầu thang? (nghĩa là leo đến bậc thang thứ $N$). Bờm muốn nhờ bạn trả lời câu hỏi này.
#### Input
- Dòng đầu tiên: gồm 2 số nguyên $N$ và $K$, là số bậc của cầu thang và số bậc thang bị hỏng.
- Dòng thứ hai: gồm $K$ số nguyên cho biết chỉ số của các bậc thang bị hỏng theo thứ tự tăng dần.
#### Output
- In ra phần dư của số cách Lucky leo hết cầu thang khi chia cho $14062008$.
#### Sample Input

4 2
2 3

#### Sample Output

0

#### Giới hạn
- $0 \le K < N \le 10^5$.
#### Giải thích
- Vì bậc $2, 3$ bị hỏng, ta không thể leo từ bậc $1$ đến ô $N$.
#### Lời giải
:::spoiler **Ý tưởng**
- Gọi $dp_i$ là số cách để leo từ bậc $1$ đến bậc $n$.
- Kết quả của bài toán là $dp_n$.
- Trường hợp cơ sở:
- Nếu ô $1$ bị thủng thì $dp_1 = 0$, nếu không thì $dp_1 = 1$.
- Nếu ô $2$ bị thủng thì $dp_2 = 0$, nếu không thì $dp_2 = 1$.
- Nếu ô thứ $i$ bị thủng: ta không thể nhảy vào ô thứ $i$, $dp_i = 0$.
- Nếu ô thứ $i$ không bị thủng: Vì ta có thể nhảy $1$ hoặc $2$ ô, $dp_i = dp_{i-1} + dp_{i-2}$.
- Tuy nhiên, vì kết quả lớn, đề bài yêu cầu ta in kết quả chia dư cho $14062008$.
- Ta thay đổi cách gọi $dp_i$ là số cách để leo từ bậc $1$ đến bậc $n$, chia dư cho $14062008$.
- Áp dụng các quy tắc đồng dư, chia dư ở mỗi trạng thái trong công thức ban đầu kết quả cuối cùng vẫn đúng do công thức chỉ có phép $+$.
:::
:::spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

int n, m;
int d[100005],dp[100005];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= k; ++i)
    {
        int x;
        cin >> x;
        d[x] = 1;
    }
    if (d[1]) dp[1] = 0;
    else dp[1] = 1;
    if (d[2]) dp[2] = 0;
    else dp[2] = 1;
    for (int i = 3; i <= n; ++i)
    {
        if (d[i]) dp[i] = 0;
        else dp[i] = (dp[i - 1] + dp[i - 2]) % 14062008;
    }
    cout << dp[n] << endl;
}

:::
# Tổng kết
Qua bài viết này, chúng ta đã biết được:
* Khái niệm và cách áp dụng cơ bản của **Quy hoạch động**.
* Khái niệm của **Trạng thái**, **Công thức truy hồi** cũng như **Trường hợp cơ sở** và cách áp dụng chúng để sử dụng **Quy hoạch động** hiệu quả.
* Cách biểu diễn **Công thức truy hồi** và phương pháp tiếp cận các bài toán **Quy hoạch động**.
* Những lỗi thường gặp khi sử dụng **Quy hoạch động** mà chúng ta cần chú ý để tránh gặp phải.

Quy hoạch động là một kĩ thuật được áp dụng rất nhiều trong lập trình thi đấu và thường xuyên xuất hiện trong các kì thi như tuyển sinh 10 hay học sinh giỏi. Vì thế, ta cần sử dụng thành thạo kĩ thuật này để có thể đạt được những kết quả tốt trong các kì thi quan trọng.
# Hướng dẫn tự học

| Bước | Nội dung chi tiết |
|:----:|:--------------------------------------------------------------------------------------------------------------------------------------- |
| 1 | - Đọc tài liệu, kết hợp xem hình ảnh để hiểu nội dung.<br>- Khi gặp bài toán: thử dành vài phút đọc đề, suy nghĩ trước khi xem lời giải. |
| 2 | - Giải bài tập dựa trên lý thuyết.<br>- Xem ý tưởng và cách cài đặt (nếu cần). |