Tác giả:
- Hà Phước Vũ - Lớp $9/5$, trường THCS Tây Sơn, Đà Nẵng.
Người kiểm thử:
- Phạm Lê Minh Sơn - Lớp $9/1$, trường THCS Trưng Vương, Đà Nẵng.
- Nguyễn An Phước - Lớp $9/1$, trường THCS Trưng Vương, Đà Nẵng.
- Trần Tiến Khoa - Lớp $9/3$, trường THCS Lương Thế Vinh, Đà Nẵng.
- Nguyễn Văn Anh Kiệt - Lớp $9/6$, trường THCS Phan Đình Phùng, Đà Nẵng.
- Bùi Minh Nguyên - Lớp $9/11$, trường THCS Huỳnh Thúc Kháng, Đà Nẵng.
Nguồn tham khảo của bài viết.
- [VNOI - Quy hoạch động](https://vnoi.info/wiki/algo/dp/basic-dynamic-programming-1.md).
- [Codeforces - Everything about Dynamic Programming](https://codeforces.com/blog/entry/43256).
## I. Giới thiệu.
Quy hoạch động (gọi tắt là Dp) là một thuật toán được sử dụng rất phổ biến bởi độ phức tạp của nó. Ưu điểm của Dp là nó dùng kết quả đã tính sẵn và tính cho các kết quả tiếp theo. Vì thế Dp có độ phức tạp thấp hơn các thuật toán như quay lui, cày trâu, ...
Dp có rất nhiều dạng và phổ biến như Mặt nạ bit (hay là Bitmask), Chữ số, Hoán vị, Bao lồi, ... Tuy nhiên, ta sẽ không đề cập đến nó ở đây mà chỉ đề cập đến Dp cơ bản và mở rộng một chút về Dp.
## II. Một số bài toán về Dp.
Để hiểu về Dp, ta có thể xem qua các ví dụ sau.
### 1. Ví dụ 1.
Bài toán có nội dung như sau:
> Cho $1$ số nguyên dương $n$ $(1 \le n \le 10^5)$, hãy tìm số Fibonacci thứ $n$.
#### Cách giải bằng đệ quy.
Gọi $F(i)$ là số Fibo thứ $i$, dễ dàng thấy $F(i) = F(i-1)+F(i-2)$ và $F(1) = F(2) = 1$.
Với ý tưởng đơn giản trên, ta có thể giải nó như sau.
```cpp=
int F(int n) {
if (n == 1 || n == 2) return 1;
return F(n-1)+F(n-2);
}
```
Với cách giải trên, ta dễ dàng thấy ta chỉ có thể giải với $1 \le n \le 20$, không phù hợp để giải bài toán ban đầu.
#### Cách giải bằng Dp.
Ta nhận thấy rằng, để tính $F(i)$ thì ta cần $F(i-1)$ và $F(i-2)$. Và để tính $F(i-1)$ thì ta lại cần $F(i-2)$ và $F(i-3)$. Dễ dàng nhận thấy $F(i-2)$ trong $2$ trường hợp trên đã được tính tới $2$ lần.
Để giải quyết vấn đề trên, sau khi tính kết quả cho $F(i)$ thì ta sẽ lưu nó lại để tính cho những trường hợp sau. Khi đó, ta có thể giải nó như sau.
```cpp=
int fibo[100000]{-1};
int F(int n) {
if (n == 1 || n == 2) return 1;
else if (fibo[n] != -1) return fibo[n];
fibo[n] = F(n-1)+F(n-2);
return fibo[n];
}
```
Ta có thể khử đệ quy như sau.
```cpp=
int fibo[100000];
int F(int n) {
fibo[1] = fibo[2] = 1;
for (int i = 3; i <= n; i++) {
fibo[i] = fibo[i-1]+fibo[i-2];
}
return fibo[n];
}
```
Cách giải trên có độ phức tạp là $O(n)$, phù hợp để giải với giới hạn $1 \le n \le 10^5$.
### 2. Ví dụ 2.
- Bạn có thể thử giải ở [đây](https://lqdoj.edu.vn/problem/liq).
Bài toán có nội dung như sau:
> Cho dãy $a$ gồm $n$ phần tử $a_1, a_2, ..., a_n$ $(1 \le n \le 10^3)$, hãy tìm dãy con tăng dài nhất của nó.
#### Cách giải bằng đệ quy.
Gọi $F(i)$ là dãy con tăng dài nhất chứa $a_i$ là phần tử lớn nhất. Khi đó, ta sẽ xét $2$ trường hợp sau:
- $F(i) = 1$ không có dãy con tăng nào thỏa mãn.
- $F(i) = max(F(j)+1)$ với $a_j < a_i$, khi đó ta sẽ thêm $a_i$ vào dãy con tăng dài nhất chứa $a_j$.
Với ý tưởng đơn giản trên, ta có thể giải nó như sau.
```cpp=
int F(int a[], int i) {
if (i == 1) return 1;
int ans = 1;
for (int j = 1; j < i; j++) {
if (a[j] < a[i]) {
ans = max(ans, F(a, j)+1);
}
}
return ans;
}
```
Kết quả của bài toán khi đó sẽ là kết quả lớn nhất của $F(1), F(2), ..., F(n)$.
Với cách giải trên, ta dễ dàng thấy ta chỉ có thể giải với $1 \le n \le 20$, không phù hợp để giải bài toán ban đầu.
#### Cách giải bằng Dp.
Cũng như bài toán Số Fibo ở trên, ta dễ dàng thấy $F(i)$ được tính lại rất nhiều lần. Để giải quyết điều này, ta cũng sẽ làm như trên. Khi đó, ta có thể giải nó như sau.
```cpp=
int lis[1000]{-1};
int F(int a[], int i) {
if (i == 1) return 1;
else if (lis[i] != -1) return lis[i];
int ans = 1;
for (int j = 1; j < i; j++) {
if (a[j] < a[i]) {
ans = max(ans, F(a, j)+1);
}
}
lis[i] = ans;
return lis[i];
}
```
Ta có thể khử đệ quy như sau.
```cpp=
int lis[1000];
int F(int arr[], int i) {
lis[i] = 1;
for (int j = 1; j < i; j++) {
if (a[j] < a[i]) {
lis[i] = max(lis[i], lis[j]+1);
}
}
return lis[i];
}
```
Cách giải trên có độ phức tạp là $O(n^2)$, phù hợp để giải với giới hạn $1 \le n \le 10^3$.
### 3. Ví dụ 3.
- Bạn có thể thử ở [đây](https://tleoj.edu.vn/problem/edu009d).
Bài toán có nội dung như sau.
> Cho $n$ loại đồng xu $(1 \le n \le 10^3)$, đồng thứ $i$ có giá là $a_i$. Hày tìm số lượng đồng xu ít nhất cần sử dụng để tổng của chúng là $S$ $(1 \le S \le 10^3)$.
#### Cách giải bằng đệ quy.
Cái này mình sẽ không đề cập tới nữa.
#### Cách giải bằng Dp.
Gọi $Dp[i]$ là số lượng đồng xu ít nhất cần sử dụng để tống của chúng là $i$. Khi đó, ta sẽ có $2$ trường hợp sau.
- $Dp[i] = inf$ nếu không có cách chọn.
- $Dp[i] = min(Dp[i-a_j]+1)$ với mọi $a_j \le i, dp[i-a_j] \neq inf$.
Tại sao lại có $Dp[i] = Dp[i-a[j]]+1$? Nếu chọn đồng xu $a_j \le i$, ta sẽ cần thêm những đồng xu có tổng là $i-a_j$ để có tổng là $i$. Dễ thấy nếu số lượng đồng xu ít nhất cần sử dụng để tổng của chúng là $i-a_j$, thì $i$ cũng sẽ tương tự. Vì vậy ta có $Dp[i] = Dp[i-a[j]]+1$ với $1$ là đồng xu $a_j$.
Khi đó, đáp án của chúng ta sẽ là $Dp[S]$.
Dưới đây là code tham khảo với độ phức tạp thời gian là $O(n \times S)$.
```cpp=
int Dp[1000];
int solve(int arr[], int n, int s) {
for (int i = 1; i <= S; i++) {
Dp[i] = inf;
for (int j = 1; j <= n; j++) {
if (Dp[i-a[j]] != inf && a[j] <= i) {
Dp[i] = min(Dp[i-a[j]]+1, Dp[i]);
}
}
}
if (Dp[S] == inf) {
return -1;
}
return Dp[S];
}
```
## III. Nhận xét về Dp.
### 1. Khi nào sử dụng Dp.
Từ những ví dụ trên, ta dễ dàng thấy Dp sử dụng để giải một bài toán bằng cách sử dụng kết quả từ những bài toán con có giới hạn đầu vào nhỏ hơn (hay là bài toán gối nhau).
### 2. Công thức truy hồi.
Để giải một bài toán bằng Dp, ta cần phải tìm được mối liên hệ giữa kết quả cần tìm và kết quả con. Ví dụ như bài toán Số Fibo ở trên có công thức truy hồi như sau:
- $Dp[1] = Dp[2] = 1$.
- $Dp[i] = Dp[i-1]+Dp[i-2]$.
Kết quả của mỗi bài $Dp$ thường sẽ là kết quả ở vị trí $n$, kết quả lớn nhất, kết quả nhỏ nhất, $...$ tùy vào yêu cầu của bài.
## IV. Luyện tập về Dp.
### 1. Bài toán 1.
- Đề bài tại [đây](https://oj.vnoi.info/problem/atcoder_dp_d).
Mình khuyên bạn nên thử sức trước khi đọc hướng dẫn nha.
Gọi $Dp[i]$ là cách chọn các đồ vật có tổng khối lượng là $i$ và tổng giá trị của chúng là lớn nhất.
Nếu như ta chọn một đồ vật có khối lượng $w_j$ và giá trị là $v_j$ để có tổng khối lượng các đồ vật đã chọn là $i$, ta sẽ có công thức như sau:
- $Dp[i] = Dp[i-w_j]+v_i$ với $w_j \le i$.
Từ đó, ta có công thức truy hồi như sau:
- $Dp[i] = max(Dp[i-w_j]+v_i)$ với $w_j \le i$.
Khi đó, kết quả cần tìm sẽ là $max(Dp[1],$ $Dp[2],$ $...,$ $Dp[W])$.
Dưới đây là code tham khảo với độ phức tạp là $O(n \times W)$.
```cpp=
int Dp[100000]{inf};
int solve(int n, int W, int w[], int v[]) {
Dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = W; j >= w[i]; j--) {
Dp[j] = max(Dp[j], Dp[j-w[i]]+v[i]);
}
}
return Dp[W];
}
```
### 2. Bài toán 2.
- Đề bài tại [đây](https://lqdoj.edu.vn/problem/stonefrog2).
Mình khuyên bạn nên thử sức trước khi đọc hướng dẫn nha.
Gọi $Dp[i]$ là số chi phí ít nhất để di chuyển từ ô $1$ đến ô $i$. Khi đó, ta sẽ có công thức truy hồi như sau:
- $Dp[i] = 0$ nếu $i = 1$.
- $Dp[i] = min(Dp[j]+abs(a_i-a_j))$ $(1 \le i-j \le k)$ nếu ta chọn nhảy từ ô $j$ sang ô $i$.
Kết quả của chúng ta khi đó sẽ là $Dp[n]$.
Dưới đây là code tham khảo với độ phức tạp thời gian là $O(n \times k)$, bộ nhớ là $O(n)$.
```cpp=
int Dp[100000]{inf};
int solve(int a[], int n, int k) {
Dp[1] = 0;
for (int i = 2; i <= n; i++) {
for (int j = max(1, i-k); j <= i-1; j++) {
Dp[i] = min(Dp[i], Dp[j]+abs(a[i]-a[j]));
}
}
return Dp[n];
}
```
### 3. Bài toán 3.
- Đề bài tại [đây](https://codeforces.com/problemset/problem/189/A).
Mình khuyên bạn nên thử sức trước khi đọc hướng dẫn nha.
Gọi $Dp[i]$ là số lượng miếng băng nhiều nhất cần sử dụng để tạo thành $1$ băng độ dài $i$. Khi đó, ta sẽ có công thức truy hồi cực kì ngắn gọn như sau.
- $Dp[i] = Dp[i-a]+1$ nếu chọn $1$ băng độ dài $a$, khi đó ta sẽ cần $1$ băng có độ dài là $i-a$.
- $Dp[i] = Dp[i-b]+1$ nếu chọn $1$ băng độ dài $b$, khi đó ta sẽ cần $1$ băng có độ dài là $i-b$.
- $Dp[i] = Dp[i-c]+1$ nếu chọn $1$ băng độ dài $c$, khi đó ta sẽ cần $1$ băng có độ dài là $i-c$.
Khi đó đáp án của chúng ta sẽ là $Dp[n]$.
Dưới đây là code tham khảo có độ phức tạp thời gian và bộ nhớ là $O(n)$.
```cpp=
int Dp[4001];
int solve(int n, int a, int b, int c) {
for (int i = 1; i <= n; i++) {
if (a <= i) Dp[i] = max(Dp[i], Dp[i-a]+1);
if (b <= i) Dp[i] = max(Dp[i], Dp[i-b]+1);
if (c <= i) Dp[i] = max(Dp[i], Dp[i-c]+1);
}
return Dp[n];
}
```
### 4. Bài toán 4.
- Đề bài tại [đây](https://lqdoj.edu.vn/problem/cses1745).
Mình khuyên bạn nên thử sức trước khi đọc hướng dẫn nha.
Gọi $Dp[s]$ là Boolean kiểm tra liệu ta có thể tạo tổng $s$ từ các đồng xu đã cho. Khi đó, ta sẽ có công thức truy hồi như sau:
- $Dp[s] = True$ nếu tồn tại vị trí $i$ thỏa mãn $a_i = s$.
- $Dp[s] = Dp[s-a_i]$ nếu tồn tại vị trí $i$ thỏa mãn $a_i < s$.
Lưu ý rằng với trường hợp $Dp[i] = Dp[i-a_j]$ thì nếu $Dp[i] = True$ mà $Dp[i-a_j] = False$, ta vẫn sẽ gán $Dp[s] = True$ bởi trước đó đã tồn tại một cách tạo tổng $s$.
Kết quả của chúng ta là các giá trị $s$ thỏa mãn $Dp[s] = True$. Vì tổng lớn nhất tạo được sẽ là $\sum_{i = 1}^n a_i$ nên $1 \le s \le \sum_{i = 1}^n a_i$.
Dưới đây là code tham khảo có độ phức tạp thời gian là $O(n \times (a_1+a_2+...+a_n))$, bộ nhớ là $O(a_1+a_2+...+a_n)$.
```cpp=
int Dp[100000];
void solve(int n, int a[]) {
for (int i = 1; i <= n; i++) {
for (int s = S; s >= 0; s--) {
if (a[i] == s) Dp[s] = 1;
else if (a[i] < s) Dp[s] = max(Dp[s], Dp[s-a[i]]);
}
}
vector<ll> ans;
for (int s = 1; s <= S; s++) {
if (Dp[s] == 1) ans.push_back(x);
}
cout << ans.size() << "\n";
for (auto const& x : ans) {
cout << x << " ";
}
return;
}
```
### 5. Luyện tập.
Sau đây là một số bài bạn có thể giải thử để luyện tập, ở đây mình chỉ chọn những bài toán mình nghĩ là phù hợp nên thông cảm.
- [TLEoj - Trò chơi](https://tleoj.edu.vn/problem/edu007c).
- [TLEoj - Bữa tiệc](https://tleoj.edu.vn/problem/1a).
- [LQDOJ - Đua xe](https://lqdoj.edu.vn/problem/carrace).
- [LQDOJ - Hoán vị](https://lqdoj.edu.vn/problem/lqdojcontest8bai3).
- [VNOJ - Bậc thang](https://oj.vnoi.info/problem/vsteps).
- [TLEoj - Elementals](https://tleoj.edu.vn/problem/51c).
- [Codeforces - 1926C](https://codeforces.com/problemset/problem/1926/C).
- [LQDOJ - Help Conan 12!](https://lqdoj.edu.vn/problem/maxarr01).
## V. Mở rộng hơn về Dp.
- Ta sẽ tìm hiểu sâu hơn về Dp, cụ thể là tìm hiểu các loại thường gặp của Dp.
### 1. Đa chiều.
- Đây là loại Dp thường gặp nhất trong đa số các kì thi tin.
- Đa số sẽ là Dp $2$ đến $3$ chiều, nhiều chiều hơn thường là Dp chữ số.
#### 1. Ví dụ 1.
- Đề bài tại [đây](https://oj.vnoi.info/problem/qbstr).
Gọi $Dp[i][j]$ là xâu con chung dài nhất của xâu $s_1s_2...s_{i}$ và $t_1t_2...t_{j}$. Khi đó, ta sẽ có công thức truy hồi như sau.
- $Dp[0][j] = Dp[i][0]$ là xâu rỗng.
- $Dp[i][j] = Dp[i-1][j-1]+1$ nếu $s_i = t_j$. Nếu $s_i = t_j$, ta sẽ nối $s_i$ vào xâu con chung dài nhất của $2$ xâu $s_1s_2...s_{i-1}$ và $t_1t_2...t_{j-1}$ để được một xâu mới dài hơn.
- $Dp[i][j] = max(Dp[i-1][j], Dp[i][j-1])$ nếu ta không thêm $s_i$ hoặc $t_j$ vào xâu con chung dài nhất trước đó, đơn giản là vì $s_i \neq t_j$.
Khi đó, đáp án của chúng ta sẽ là $Dp[|s|][|t|]$.
Dưới đây là code tham khảo có độ phức tạp thời gian và bộ nhớ là $O(|s| \times |t|)$.
```cpp=
int Dp[2000][2000]{0};
int solve(string s, string t) {
int n = s.size();
int m = t.size();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i] == t[j]) 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];
}
```
#### 2. Ví dụ 2.
- Đề bài tại [đây](https://tleoj.edu.vn/problem/25c).
Gọi $Dp[i][j]$ là tổng giá trị trên đường đi từ ô $(1, 1)$ đến ô $(i, j)$ lớn nhất có thể. Theo đề bài, ta có công thức truy hồi như sau:
- $Dp[i][j] = a[i][j]$ với $i = j = 1$ vì ta đang ở ô xuất phát.
- $Dp[i][j] = Dp[i-1][j]+a[i][j]$ với $i > 1$ vì ta nhảy đến ô $(i, j)$ từ ô $(i-1, j)$.
- $Dp[i][j] = Dp[i-1][j-1]+a[i][j]$ với $min(i, j) > 1$ vì ta nhảy đến ô $(i, j)$ từ ô $(i-1, j-1)$.
Từ nhận xét trên, dễ dàng thấy kết quả của mỗi $Dp[i][j]$ sẽ là kết quả lớn nhất từ $2$ trường hợp trên. Khi đó, kết quả của chúng ta sẽ là kết quả lớn nhất của $Dp[n][1], Dp[n][2], ..., Dp[n][n]$.
Dưới đây là code tham khảo với độ phức tạp thời gian và bộ nhớ là $O(n^2)$.
```cpp=
int Dp[1000][1000]{-inf};
int solve(int a[][], int n) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (i == 1 && j == 1) Dp[i][j] = a[i][j];
if (i > 1) Dp[i][j] = max(Dp[i][j], Dp[i-1][j]+a[i][j]);
if (min(i, j) > 1) Dp[i][j] = max(Dp[i][j], Dp[i-1][j-1]+a[i][j]);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, dp[n][i]);
}
return ans;
}
```
#### 3. Ví dụ 3.
- Đề bài tại [đây](https://tleoj.edu.vn/problem/edu022c).
Gọi $Dp[x][y]$ là số lượng dãy con tăng có độ dài $x$ chứa $a_y$ là phần tử cuối cùng. Khi đó, ta sẽ có công thức truy hồi như sau.
- $Dp[x][y] = 1$ nếu $x = 1$.
- $Dp[x][y] += Dp[x-1][z]$ với $a_z < a_y$.
Khi đó, đáp án của chúng ta sẽ là tổng các giá trị $Dp[k][x]$ với $1 \le x \le n$.
Dưới đây là code tham khảo có độ phức tạp thời gian là $O(n^2 \times k)$, bộ nhớ là $O(n \times k)$.
```cpp=
int Dp[100][100];
int solve(int a[], int n, int k) {
for (int y = 1; y <= n; x++) {
Dp[1][y] = 1;
for (int z = 1; z < y; z++) {
if (a[z] < a[y]) {
for (int x = 2; x <= k; x++) Dp[x][y] += Dp[x-1][z];
}
}
}
int ans = 0;
for (int x = 1; x <= n; x++) {
ans += Dp[k][x];
}
return ans;
}
```
#### 4. Luyện tập.
Sau đây là một số bài bạn có thể giải thử để luyện tập, ở đây mình chỉ chọn những bài toán mình nghĩ là phù hợp nên thông cảm.
- [TLEoj - Nhảy lò cò](https://tleoj.edu.vn/problem/hopping).
- [VNOJ - Permutation](https://oj.vnoi.info/problem/atcoder_dp_t).
- [TLEoj - Tổng modulo](https://tleoj.edu.vn/problem/50b).
- [LQDOJ - Cửa hàng IQ](https://lqdoj.edu.vn/problem/cuahangiq).
- [LQDOJ - Dãy chia hết](https://lqdoj.edu.vn/problem/lqdojcontest5bai4).
- [LQDOJ - Máy nghe nhạc](https://lqdoj.edu.vn/problem/23on3c22).
- [TLEoj - Số cách đi quân mã](https://tleoj.edu.vn/problem/edu008a).
- [VNOJ - Bội số chung nhỏ nhất](https://oj.vnoi.info/problem/ctnown).
- [VNOJ - Đường đi có tổng lớn nhất](https://oj.vnoi.info/problem/qbmax).
### 2. Truy vết.
- Một số bài toán giải bằng Dp không chỉ yêu cầu đưa ra kết quả tốt nhất mà còn yêu cầu đưa ra làm sao để cho ra kết quả đó. Vậy ta sẽ làm như thế nào.
#### 1. Ví dụ 1.
- Đề bài như sau (Mình không nhớ link bài):
> Cho xâu $s$ gồm $n$ kí tự $s_1s_2...s_n$ $(1 \le n \le 10^2)$, hãy chia $s$ thành các xâu đối xứng con liên tiếp thỏa mãn số lượng là ít nhất.
Gọi $Dp[i]$ là số lượng xâu đối xứng liên tiếp ít nhất sau khi chia xâu $s_1s_2...s_i$. Khi đó, ta sẽ có công thức truy hồi như sau:
- $Dp[0] = 1$ vì xâu rỗng cũng là xâu đối xứng.
- $Dp[i] = min(Dp[j-1]+1)$ $(j \le i)$ thỏa mãn $s_js_{j+1}...s_i$ là xâu đối xứng.
Khi đó, đáp án của chúng ta sẽ là $Dp[n]$.
Dưới đây là code tham khảo với độ phức tạp thời gian là $O(n^3)$, bộ nhớ là $O(n)$.
```cpp=
int Dp[100]{inf};
int solve(string s, int n) {
Dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (IsPalindrome(j, i) == True) {
Dp[i] = min(Dp[i], Dp[j-1]+1);
}
}
}
return Dp[n];
}
```
Tuy nhiên, đề bài yêu cầu ta chia xâu $s$ ra chứ không phải đếm số lượng. Vậy ta sẽ phải làm như thế nào.
Với mỗi $Dp[i]$, ta sẽ lưu $T[i]$ là vị trí $j$ thỏa mãn công thức truy hồi. Sau khi tính xong, ta sẽ dựa vào $T$ để tìm ra cách chia thỏa mãn. Dựa vào mảng $T$, ta dễ dàng thấy xâu $s_{T[i]}s_{T[i]+1}...s_i$ sẽ là một xâu đối xứng. Khi đó, ta sẽ lưu nó vào kết quả và từ $T[i]$ thì ta sẽ truy tiếp về $T[T[i]-1]$ để tiếp tục lấy các xâu đối xứng còn lại. Để dễ hình dung hơn, bạn có thể tham khảo code sau.
```cpp=
int Dp[100]{inf}, T[100];
void solve(string s, int n) {
// Tính kết quả.
Dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (IsPalindrome(j, i) == True) {
if (Dp[i] > Dp[j-1]+1) {
Dp[i] = Dp[j-1]+1;
T[i] = j;
}
}
}
}
// Truy vết.
vector<string> ans;
int pos = n; // Bắt đầu truy vết từ vị trí cuối.
while (pos > 0) {
string plr = s.substr(T[pos], pos-T[pos]+1);
ans.push_back(plr); // Lưu xâu đối xứng đã truy vết được vào dãy.
pos = T[pos]-1; // Tiếp tục truy vết đoạn còn lại.
}
reverse(ans.begin(), ans.end());
for (auto const& x: ans) {
cout << x << "\n";
}
return;
}
```
#### 2. Ví dụ 2.
- Quay lại bài [TLEoj - Đường đi ma trận](https://tleoj.edu.vn/problem/25c).
Tương tự như bài ở trên, ta sẽ gọi $T[i][j]$ là ô ta đang ở trước khi nhảy đến ô $(i, j)$. Bắt đầu từ ô $(n, i)$ thỏa mãn, ta sẽ lưu nó vào kết quả và truy tiếp về $T[n][i]$. Sau đó, ta cũng sẽ làm tương tự và khi truy về tới $T[1][1]$. Dễ dàng thấy kết quả sẽ luôn tồn tại. Để dễ hình dung hơn, bạn có thể tham khảo code sau.
```cpp=
int Dp[1000][1000]{-inf};
pair<int, int> T[1000][1000];
void solve(int a[][], int n) {
// Tính kết quả.
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (i == 1 && j == 1) {
Dp[i][j] = a[i][j];
T[i][j] = {0, 0};
}
if (i > 1 && Dp[i][j] < Dp[i-1][j]+a[i][j]) {
Dp[i][j] = Dp[i-1][j]+a[i][j];
T[i][j] = {i-1, j};
}
if (min(i, j) > 1 && Dp[i][j] < Dp[i-1][j-1]+a[i][j]) {
Dp[i][j] = Dp[i-1][j-1]+a[i][j];
T[i][j] = {i-1, j-1};
}
}
}
// Truy vết.
vector<pair<int, int>> ans;
// Tìm vị trí có kết quả thỏa mãn để bắt đầu truy vết.
int x = n, y = 0, mx = 0;
for (int i = 1; i <= n; i++) {
if (Dp[n][i] > mx) {
mx = Dp[n][i];
y = i;
}
}
// Bắt đầu truy vết từ kết quả.
while ({x, y} != {0, 0}) {
ans.push_back({x, y});
int tmp = T[x][y].fi;
y = T[x][y].se;
x = tmp;
}
reverse(ans.begin(), ans.end());
for (auto const& x: ans) {
cout << x.fi << " " << x.se << "\n";
}
return;
}
```
#### 3. Ví dụ 3.
- Quay lại bài [LQDOJ - Chú ếch và hòn đá](https://lqdoj.edu.vn/problem/stonefrog2).
Với mỗi $Dp[i]$, ta sẽ lưu $T[i]$ là vị trí $j$ thỏa mãn công thức truy hồi. Khi ở vị trí $n$, ta biết rằng ta nhảy từ vị trí $T[n]$ và ta sẽ lưu $n$ vào kết quả. Sau đó, ta sẽ truy về tiếp $T[T[n]-1]$ cho đến khi gặp được $T[1]$. Để dễ hình dung hơn, bạn có thể tham khảo code sau.
```cpp=
int Dp[100000]{inf}, T[100000]{0};
void solve(int a[], int n, int k) {
Dp[1] = 0, T[1] = 0;
for (int i = 2; i <= n; i++) {
for (int j = max(1, i-k); j <= i-1; j++) {
if (Dp[i] > Dp[j]+abs(a[i]-a[j])) {
Dp[i] = Dp[j]+abs(a[i]-a[j]);
T[i] = j;
}
}
}
vector<int> ans;
int pos = n;
while (pos > 0) {
ans.push_back(T[pos]);
pos = T[pos]-1;
}
reverse(ans.begin(), ans.end());
for (auto const& x: ans) {
cout << x << "\n";
}
return;
}
```
#### 4. Luyện tập.
Sau đây là một số bài bạn có thể giải thử để luyện tập, ở đây mình chỉ chọn những bài toán mình nghĩ là phù hợp nên thông cảm.
- [TLEoj - Tiền lì xì](https://tleoj.edu.vn/problem/46c).
- [LQDOJ - Xâu con chung dài nhất](https://lqdoj.edu.vn/problem/longescomtstr).
Số lượng bài truy vết mình giải không nhiều nên cũng không có để đề xuất.
## VI. Tối ưu Dp.
- Đây là phần khá nâng cao về Dp nên để đọc thì bạn cần hiểu hết những nội dung ở trên.
- Một số bài toán Dp sẽ có công thức truy hồi thỏa mãn một tính chất nào đấy mà ta có thể dùng một thuật toán khác để tối ưu độ phức tạp thời gian hoặc bộ nhớ.
- Ở đây ta chỉ nói đến $2$ thuật toán và $2$ kĩ thuật cơ bản đối với học sinh cấp $2$. Còn các thuật toán nâng cao khác thì bạn có thể tìm ở phần $VII$.
### 1. Tối ưu bộ nhớ.
- Khi giải một bài toán bằng Dp, ta không nhất thiết sẽ sử dụng mảng mà có thể là $1$ mảng đếm, $1$ biến, $...$ Ngoài ra trong các bài toán giải bằng Dp, có $1$ số kết quả của những bài toán con sẽ không được sử dụng nhiều.
#### 1. Ví dụ 1.
Quay lại bài số Fibo, ta có thể tìm số Fibo thứ $n$ như sau.
```cpp=
int Dp[100000];
int F(int n) {
Dp[1] = Dp[2] = 1;
for (int i = 3; i <= n; i++) {
Dp[i] = Dp[i-1]+Dp[i-2];
}
return Dp[n];
}
```
Dễ dàng thấy để tính $Dp[i]$, ta chỉ sử dụng duy nhất $Dp[i-1]$ và $Dp[i-2]$ chứ không sử dụng $Dp[1]$ đến $Dp[i-3]$. Vì vậy, việc lưu trữ toàn bộ giá trị $Dp[j] (1 \le j \le i-3)$ là không cần thiết. Và để giải quyết vấn đề trên, ta có thể làm như sau.
```cpp=
int F(int n) {
int a = b = 1, c;
if (n == 1 || n == 2) return 1;
for (int i = 3; i <= n; i++) {
c = a+b;
a = b;
b = c;
}
return b;
}
```
Độ phức tạp vẫn là $O(n)$ nhưng bộ nhớ lại là $O(1)$ thay vì $O(n)$ như trên.
#### 2. Ví dụ 2.
- Đề bài tại [đây](https://lqdoj.edu.vn/problem/linegame09).
Gọi $even[i]$ và $odd[i]$ lần lượt là cách chọn các ô để đạt số điểm lớn nhất với ô kết thúc tại $i$ lần lượt có số lượng ô được chọn là chẵn và lẻ. Khi đó, ta sẽ có công thức truy hồi như sau.
- $even[i] = 0, odd[i] = a[i]$ với $i = 1$.
- $even[i] = max(even[i-1], odd[i-1]+a[i])$ với $2 \le i \le n$.
- $odd[i] = max(odd[i-1], even[i-1]-a[i])$ với $2 \le i \le n$.
Kết quả của chúng ta khi đó sẽ là $max(even[n], odd[n])$.
Dưới đây là code tham khảo với độ phức tạp thời gian là $O(n)$, bộ nhớ là $O(n)$.
```cpp=
int even[1000000];
int odd[1000000];
int solve(int a[], int n) {
even[1] = 0;
odd[1] = a[1];
for (int i = 2; i <= n; i++) {
even[i] = max(even[i-1], odd[i-1]+a[i]);
odd[i] = max(odd[i-1], even[i-1]-a[i]);
}
return max(even[n], odd[n]);
}
```
Dễ dàng thấy để tính $even[i]$ và $odd[i]$, ta chỉ sử dụng kết quả từ $even[i-1]$ và $odd[i-1]$. Khi đó, ta có thể sử dụng $2$ biến song song để thay thế. Khi đó, ta có thể giải như sau.
```cpp=
int solve(int a[], int n) {
int a = 0, b = a[1], tmp;
for (int i = 2; i <= n; i++) {
tmp = b;
a = max(a, b+a[i]);
b = max(b, tmp-a[i]);
}
return max(a, b);
}
```
Độ phức tạp thời gian là $O(n)$, bộ nhớ là $O(1)$.
#### 3. Ví dụ 3.
- Đề bài tại [đây](https://tleoj.edu.vn/problem/52c).
Gọi $Dp[l][a_i]$ là dãy công sai có độ dài $l$ chứa $a_i$ là phần tử lớn nhất. Khi đó, ta sẽ có công thức truy hồi sau:
- $Dp[l][a_i] = 1$ với $l = 1$.
- $Dp[l][a_i]$ $+$$=$ $Dp[l-1][a_i-k]$ với $2 \le l \le m$.
Khi đó, đáp án của chúng ta sẽ là tổng các giá trị $Dp[m][a_i]$. Nhận thấy rằng $a_i \le 10^9$ nên $Dp[l]$ không thể là $1$ mảng thường mà thay vào đó, ta phải sử dụng mảng đếm.
Dưới đây là code tham khảo với độ phức tạp thời gian và bộ nhớ đều là $O(n \times m)$.
```cpp=
vector<map<int, int>> Dp(100);
int solve(int a[], int n, int m , int k) {
for (int i = 1; i <= n; i++) {
for (int l = 1; l <= m; l++) {
if (l == 1) Dp[1][a[i]] = 1;
else Dp[l][a[i]] += Dp[l-1][a-k];
}
}
int ans = 0;
for (auto const&x : Dp[m-1]) {
ans += x.second;
}
return ans;
}
```
#### 4. Ví dụ 4.
Quay lại bài xâu con chung dài nhất, ta có thể giải nó như sau.
```cpp=
int Dp[2000][2000]{0};
int solve(string s, string t) {
int n = s.size();
int m = t.size();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i] == t[j]) 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];
}
```
Dễ dàng thấy để tính $Dp[i][j]$, ta chỉ cần sử dụng $Dp[i-1][j-1], Dp[i-1][j]$ và $Dp[i][j-1]$. Khi đó, ta có thể tối ưu bộ nhớ từ $O(n \times m)$ xuống còn $O(2 \times n)$. Khi đó, ta có thể giải như sau.
```cpp=
int Dp[2000][2]{0};
int solve(string s, string t) {
int n = s.size();
int m = t.size();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i] == t[j]) Dp[i][2-j%2] = Dp[i][j%2+1]+1;
else Dp[i][2-j%2] = max(Dp[i][2-j%2], Dp[i][j%2+1]);
}
}
return Dp[n][2-m%2];
}
```
Độ phức tạp thời gian vẫn là $O(n \times m)$ nhưng bộ nhớ là $O(2 \times n)$. Tất nhiên ta có thể thay đổi để đạt độ phức tạp bộ nhớ là $O(2 \times m)$.
#### 5. Luyện tập.
Sau đây là một số bài bạn có thể giải thử để luyện tập, ở đây mình chỉ chọn những bài toán mình nghĩ là phù hợp nên thông cảm.
- [LQDOJ - Hoán vị](https://lqdoj.edu.vn/problem/lqdojcontest8bai3).
- [VNOJ - Bậc thang](https://oj.vnoi.info/problem/vsteps).
- [TLEoj - Elementals](https://tleoj.edu.vn/problem/51c).
- [TLEoj - Tổng các tích](https://tleoj.edu.vn/problem/42e).
- [LQDOJ - Dãy chia hết](https://lqdoj.edu.vn/problem/lqdojcontest5bai4).
### 2. Đảo nhãn.
- Đang viết.
### 3. Chặt nhị phân.
- Đây là một thuật toán cơ bản mà ai cũng biết nên ta sẽ không nói đến nó nữa.
#### 1. Ví dụ 1.
- Quay lại bài [Dãy con tăng dài nhất](https://hackmd.io/@flothecoder/amoguslmaosusus#2-V%C3%AD-d%E1%BB%A5-2).
Ở bài trên, ta đã giải quyết với $1 \le n \le 10^3$. Vậy nếu $1 \le n \le 10^5$ thì sao?
Ta sẽ gọi $1$ mảng $Dp$ để lưu dãy con tăng dài nhất vừa tìm được. Khi đó, với mỗi phần tử $a_i$ thì ta sẽ xét $2$ trường hợp:
- $a_i > max(Dp)$: Ta thêm $a_i$ vào cuối dãy con tăng này hay là cuối mảng $Dp$.
- $a_i < max(Dp)$: Ta tìm vị trí $pos$ thỏa mãn $Dp[pos] \ge a_i$ và đặt $Dp[pos] = a_i$. Điều này có thể thực hiện bằng Chặt nhị phân.
Sau khi thực hiện xong, đáp án của chúng ta là độ dài của mảng $Dp$.
Dưới đây là code tham khảo có độ phức tạp thời gian là $O(n \times log_2n)$, bộ nhớ là $O(n)$.
```cpp=
int solve(int n, int a[]) {
vector<int> Dp;
for (int i = 1; i <= n; i++) {
if (a[i] > Dp.back()) {
Dp.push_back(a[i]);
}
else {
int pos = lower_bound(Dp.begin(), Dp.end(), a[i])-Dp.begin();
Dp[pos] = a[i];
}
}
return Dp.size();
}
```
#### 2. Ví dụ 2.
- Đề bài tại [đây](https://tleoj.edu.vn/problem/edu021c).
Trước tiên, ta sẽ sắp xếp lại các lịch thuê theo thời gian kết thúc của nó (theo $b_i$).
Gọi $Dp[i]$ cách chọn các lịch thuê với công ty thuê cuối cùng là công ty thứ $i$ sao cho tổng tiền thuê là lớn nhất. Khi đó, ta sẽ có công thức truy hồi sau:
- $Dp[1] = A_1.c$ do chỉ mới xét $1$ lịch thuê duy nhất.
- $Dp[i] = max(Dp[j])+A_i.c$ với $j$ $(1 \le j < i)$ là thứ tự công ty có $A_j.b < A_i.a$.
Kết quả của chúng ta sẽ là $max(Dp[1], Dp[2], ..., Dp[n])$.
Độ phức tạp của ý tưởng trên là $O(n^2)$, vẫn còn quá chậm để giải quyết do $1 \le n \le 10^5$. Vì vậy, ta có thể biến đổi công thức truy hồi một chút.
Gọi $Dp[i]$ cách chọn các lịch thuê với công ty thuê cuối cùng là công ty thứ $j$ $(1 \le j \le i)$ sao cho tổng tiền thuê là lớn nhất. Khi đó, ta sẽ có công thức truy hồi sau:
- $Dp[1] = A_1.c$ do chỉ mới xét $1$ lịch thuê duy nhất.
- $Dp[i] = Dp[j]+A_i.c$ với $j$ $(1 \le j < i)$ là thứ tự công ty có $A_j.b < A_i.a$ ($j$ phải lớn nhất).
Với trường hợp thứ $2$, việc tìm vị trí $j$ thỏa mãn có thể giải quyết bằng Chặt nhị phân mà ai cũng có thể làm được. Nếu bạn thắc mắc tại sao $j$ phải lớn nhất thì khi đó, ta sẽ xét được tất cả trường hợp $1 \le k \le j$ mà $A_k.b < A_i.a$ để tránh xót trường hợp. Vì $Dp[j]$ đã là lớn nhất nên chắc chắn $Dp[i]$ sẽ lớn nhất.
Với cách tối ưu trên, ta đã giải quyết bài toán với độ phức tạp nhỏ hơn là $O(n \times log_2n)$. Kết quả của chúng ta sẽ là $Dp[n]$.
Dưới đây là code tham khảo với độ phức tạp thời gian là $O(n \times log_2n)$, bộ nhớ là $O(n)$.
```cpp=
int Dp[100000];
struct node {int a, b, c;} A[100000];
bool cmp(const node& x, const node& y) {return x.b < y.b || (x.b == y.b && x.a < y.a);}
int solve(int n, node A[]) {
sort(A, A+n, cmp);
dp[1] = A[1].c;
for (int i = 2; i <= n; i++) {
int l = 1, r = i-1, j = 0;
while (l <= r) {
int m = (l+r)/2;
if (A[m].b < A[i].a) {
j = m;
l = m+1;
}
else {
r = m-1;
}
}
dp[i] = max(dp[i-1], dp[j]+A[i].c);
}
return dp[n];
}
```
##### Bonus: Bạn có thể thử code truy vết của bài trên được không?
#### 3. Luyện tập.
- [LQDOJ - Dãy Fibonacci](https://lqdoj.edu.vn/problem/fibodistribute).
- [TLEoj - Thử thách robot](https://tleoj.edu.vn/problem/edu023d).
- [TLEoj - Phần thưởng](https://tleoj.edu.vn/problem/57d).
Ở mức độ học sinh cấp $2$ thì các bài Dp tối ưu bằng Chặt nhị phân không nhiều nên số lượng bài được đề xuất luyện tập sẽ khá ít.
### 4. Cây phân đoạn.
- Để hiểu được các ví dụ sau, các bạn phải mặc định biết [Cây phân đoạn (Segment Tree)](https://vnoi.info/wiki/algo/data-structures/segment-tree-extend.md) là gì.
- Ngoài Cây phân đoạn ra, ta còn có thể sử dụng [Cây chỉ số nhị phân (Fenwick Tree)](https://vnoi.info/wiki/algo/data-structures/fenwick.md) nhưng theo mình thì biết Cây phân đoạn là đủ.
- Thật ra có thể dùng Stack trong một số trường hợp nhưng mình ghét Stack và Cây phân đoạn có nhiều ứng dụng hơn (nói riêng về việc tối ưu Dp).
#### 1. Ví dụ 1.
- Đề bài tại [đây](https://lqdoj.edu.vn/problem/dplis1).
Dựa vào cách giải của bài [Dãy con tăng dài nhất ở trên](https://hackmd.io/@flothecoder/amoguslmaosusus#C%C3%A1ch-gi%E1%BA%A3i-b%E1%BA%B1ng-Dp1), gọi $Dp[i]$ là dãy con tăng có tổng lớn nhất với phần tử cuối là $a_i$. Khi đó, ta sẽ có công thức truy hồi như sau:
- $Dp[i] = max(Dp[j])+a_i$ với $a_j < a_i$ $(1 \le j < i)$.
Khi đó, đáp án của chúng ta sẽ là $max(Dp[1], Dp[2], ..., Dp[n])$. Tuy nhiên với cách giải trên, độ phức tạp thời gian sẽ là $O(n^2)$. Dễ thấy với giới hạn của bài thì đây không phải cách giải tối ưu.
Gọi $Dp[a_i]$ là dãy con tăng có tổng lớn nhất với phần tử cuối có giá trị là $a_i$. Khi đó, ta sẽ có công thức truy hồi như sau:
- $Dp[a_i] = max(Dp[1], Dp[2], ..., Dp[a_i-1])+a_i$.
Đáp án của chúng ta sẽ là giá trị lớn nhất của $Dp$.
Để lấy giá trị lớn nhất của đoạn $[1, a_i-1]$ trên mảng $Dp$, ta sẽ sử dụng Cây phân đoạn để truy vấn trong $O(log_2a_i)$. Khi đó, độ phức tạp sẽ là $O(n \times log_2a_i)$ và đủ để giải quyết bài này.
Ở bài trên, ta thấy $1 \le a_i \le 10^9$ nên việc tạo một Cây phân đoạn $Dp$ là không thể. Vì vậy, ta sẽ sử dụng kĩ thuật Nén số (Coordinate Compression) để nén dãy $a$ lại. Dễ hiểu thì với dãy $a = [6, 9, 4, 2, 0]$, ta sẽ nén lại thành $1$ dãy $b = [\{1, 0\}, \{2, 2\}, \{3, 4\}, \{4, 6\}, \{5, 9\}]$. Để làm điều này, ta chỉ việc sử dụng Đếm phân phối hoặc Chặt nhị phân.
Dưới đây là code tham khảo với độ phức tạp thời gian là $O(n \times log_2a_i)$, bộ nhớ là $O(4\times n)$.
```cpp=
int Dp[400000]; // Đóng vai trò là mảng Dp và cả Cây phân đoạn.
// Lược bỏ phần cài đặt Cây phân đoạn.
void update_point(int node, int l, int r, int u, int v) {
// Tự code.
}
int query_max(int node, int l, int r, int u, int v) {
// Tự code.
}
int solve(int n, int a[]) {
int b[n]{0};
for (int i = 1; i <= n; i++) {
b[i] = a[i];
}
sort(b, b+n);
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(b, b+n, a[i])-b+1;
}
for (int i = 1; i <= n; i++) {
update_point(1, 1, n, a[i], query_max(1, 1, n, 1, a[i]-1)+b[a[i]]);
}
return query_max(1, 1, n, 1, n);
}
```
##### Bonus: Bạn có thể thử code truy vết của bài trên được không?
#### 2. Ví dụ 2.
- Đề bài tại [đây](https://tleoj.edu.vn/problem/49c).
Gọi $Dp[i]$ là số địa điểm nhiều nhất có thể tham quan khi xuất phát từ điểm thứ $i$. Khi đó, ta sẽ có công thức truy hồi như sau:
- $Dp[i] = max(Dp[l_i], Dp[l_i+1], ..., Dp[r_i])+1$ với $1$ là địa điểm $i$.
- Lưu ý vì xuất phát từ địa điểm thứ $i$ nên ta sẽ tính từ $n$ về $1$.
Khi đó, đáp án của chúng ta sẽ là $Dp[1]$. Tuy nhiên độ phức tạp thời gian của cách trên là $O(n \times (r_i-l_i+1))$, rõ ràng là chưa đủ để giải quyết bài này.
Ở công thức truy hồi trên, để lấy $max(Dp[l_i], Dp[l_i+1], ..., Dp[r_i])$, ta có thể tạo một Cây phân đoạn $Dp$ và thao tác trực tiếp trên đó. Khi đó, độ phức tạp thời gian sẽ giảm xuống còn $O(n \times log_2(r_i-l_i+1))$. Đáp án của chúng ta thì vẫn sẽ là $Dp[1]$.
Dưới đây là code tham khảo với độ phức tạp thời gian là $O(n \times log_2(r_i-l_i+1))$, bộ nhớ là $O(4\times n)$.
```cpp=
int Dp[800000]; // Đóng vai trò là mảng Dp và cả Cây phân đoạn.
// Lược bỏ phần cài đặt Cây phân đoạn.
void update_point(int node, int l, int r, int u, int v) {
// Tự code.
}
int query_max(int node, int l, int r, int u, int v) {
// Tự code.
}
int solve(int n, int l[], int r[]) {
for (int i = n-1; i >= 1; i--) {
update_point(1, 1, n, i, query_max(1, 1, n, l[i], r[i])+1);
}
return query_max(1, 1, n, 1, 1);
}
```
#### 3. Luyện tập.
- [TLEoj - Hộp kẹo](https://tleoj.edu.vn/problem/44b).
- [LQDOJ - Xếp bóng](https://lqdoj.edu.vn/problem/xepbong).
- [Codeforces - 1941E](https://codeforces.com/problemset/problem/1941/E).
- [TLEoj - Phần thưởng](https://tleoj.edu.vn/problem/57d).
- [LQDOJ - Dãy con tăng](https://lqdoj.edu.vn/problem/lmhis).
- [VNOJ - Dãy nghịch thế độ dài K](https://oj.vnoi.info/problem/kinv).
- [CSES - Increasing Subsequence II](https://lqdoj.edu.vn/problem/cses1748).
### 5. Một số thuật toán khác.
Ngoài $2$ thuật toán trên ra, một số bài Dp có công thức truy hồi có thể tối ưu bằng $2$ con trỏ, sử dụng `map`, mảng cộng dồn, $...$ nhưng $2$ thuật trên là thường gặp nhất. Các thuật còn lại thì khá ít nhưng các bạn vẫn nên thử với nó.
Không chỉ có tối ưu Dp bằng cách sử dụng thuật toán khác, bạn có thể tối ưu Dp bằng cách tối ưu chính công thức truy hồi của nó để giảm độ phức tạp thời gian, bộ nhớ, $...$ dựa vào các tính chất mà công thức ấy có.
## VII. Tổng kết.
Đây chỉ là bài viết về Dp cơ bản, còn về những dạng khác thì bạn có thể tìm trên các trang khác.
Bài tập về Dp khá đa dạng và phong phú nên bạn có thể kiếm để luyện tập nhiều hơn. Một số trình chấm gợi ý là Codeforces, VNOJ, TLEoj, LQDOJ, ... và CSES - Dynamic Programming.
Tóm lại, Dp là một thuật toán khá khó để học. Chúc các bạn học tập tốt và nhanh thành thạo Dp.
Các nguồn tài liệu học tập nên tham khảo.
- [VNOI - Một số bài toán Dp điển hình](https://vnoi.info/wiki/algo/dp/basic-problems.md).
- [VNOI - Một số kĩ thuật tối ưu hóa Dp](https://vnoi.info/wiki/algo/dp/Mot-so-ky-thuat-toi-uu-hoa-thuat-toan-Quy-Hoach-Dong.md).
Sign in with Wallet
Connect another wallet