---
title:
Quy hoạch động (Phần 2: Quy hoạch động LIS)
---

Quy hoạch động (Phần 2: Quy hoạch động LIS)
===

---

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

---

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

# Giới thiệu chung

- Ở phần 1, ta đã tìm hiểu và làm quen được với kĩ thuật quy hoạch động cơ bản. Ở phần này, ta sẽ làm quen với 1 bài toán khác được coi là "kinh điển" của kĩ thuật quy hoạch động - dãy con tăng dài nhất (LIS).

# [Bài toán 1](https://oj.vnoi.info/problem/liq)

## Đề bài

- Cho một dãy số gồm $n$ phần tử, tìm độ dài của dãy con tăng dài nhất của dãy được cho.

*Dãy con của một dãy là dãy số thu được bằng cách bỏ đi một số (hoặc không bỏ) phần tử của dãy ban đầu.*
*Dãy con tăng dài nhất của một dãy số là dãy con sao cho mọi phần tử liền sau lớn đều hơn phần tử liền trước nó và có độ dài lớn nhất.*

### Input
- Dòng đầu tiên gồm một số nguyên dương $n$ ($1 \le n \le 1000$) - số lượng phần tử của dãy số.
- Dòng thứ hai gồm $n$ phần tử $a_i$ ($a_i \le 10^4$) - phần tử của dãy số.

### Output
- Một số nguyên dương là độ dài của dãy con tăng dài nhất.

### Sample Input

6
1 2 5 4 6 2

### Sample Output

4

### Giải thích
- Dãy con dài nhất là dãy $a_1 = 1 < a_2 = 2 < a_4 = 4 < a_5 = 6.$

## Tiếp cận 1: Duyệt trâu
- Ta sẽ xét mọi dãy con không rỗng của dãy ban đầu và kiểm tra xem dãy con này có thỏa mãn điều kiện dãy con tăng hay không, nếu có ta sẽ lấy độ dài lớn nhất.
- Tuy nhiên cách làm này không hề hiệu quả, vì số dãy con cần xét lên đến $2^n$, không khả thi với giới hạn đề bài.

## Tiếp cận 2: Quy hoạch động

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

- Gọi $f_i$ là độ dài dãy con tăng dài nhất kết thúc tại vị trí $i$. Vì mỗi phần tử có thể được xem là một dãy con tăng có độ dài là $1$ nên trường hợp cơ sở là $f_i = 1$ với mọi $1 \le i \le n$.

### Công thức truy hồi
- Với chỉ số $j$ bất kì sao cho $j < i$ và $a_j < a_i$, ta có thể chọn phần tử vị trí $i$ ngay sau phần tử ở vị trí $j$.
- Lúc này nếu chọn phần tử ở vị trí $i$ ngay sau vị trí $j$, độ dài lớn nhất ta có được trong trường hợp này sẽ là $f[j]+1$. Vì thế ta có công thức sau với mọi $1 \le j < i$ và $a_j < a_i$:
*$$f_i = max(f_j+1)$$*
- Vì giới hạn thấp ($n \le 1000$) nên để tính $f_i$, ta có thể duyệt mọi vị trí $j$ từ $1 \rightarrow i-1$ và tìm vị trí thỏa mãn điều kiện ở trên và có $f_j+1$ là lớn nhất để cập nhập $f_i$;
- Đô phức tạp: Mỗi lần duyệt phần tử $i$, ta phải duyệt thêm 1 lần tìm vị trí $j$ nên độ phức tạp tổng là $O(n^2)$.

:::spoiler Code mẫu

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int a[n + 1], f[n + 1], ans = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        ans = max(ans, f[i]);
    }
    
    cout << ans;
    return 0;
}

:::

## Cải tiến bằng tìm kiếm nhị phân

Ở lần này, chúng ta tăng giới hạn của $n$ lên thành $\leq 10^6$. Lúc này thuật toán $O(n^2)$ không còn hiệu quả nữa mà ta cần phải cải thiện nó. Bây giờ ta tối ưu thuật toán một chút :
- Khi xét tới vị trí $i$ của dãy, giả sử ta đang có dãy $b$ độ dài $k$ : $b_1 < b_2 < b_3 < ... < b_k$ đang là dãy con tăng dài nhất tìm được thỏa mãn sao cho giá trị $b_k$ là **nhỏ nhất** có thể.
- Vì sao cần phải nhỏ nhất có thể ? Khi ta xét tiếp giá trị $a_{i + 1}$, chắc hẳn nếu ta có thể mở rộng dãy $b$ nếu $b_k < a_{i + 1}$ thì cách tối ưu nhất là mở rộng từ giá trị $b_k$ nhỏ nhất.
- Khi $b_k < a_i$ thì ta sẽ trực tiếp mở rộng dãy $b$ thành $b_1 < b_2 < b_3 < ... b_k < b_{k + 1} = a_i$
- Nếu không ta sẽ **tham lam** bằng cách tìm vị trí $j$ nhỏ nhất sao cho $b_j \geq a_i$ rồi thay thế $b_j = a_i$.
- **Chứng minh 1:** Giả sử có nhiều $b_k$ thỏa mãn nhưng không phải nhỏ nhất, nếu ta duy trì mảng $b$ mà để giá trị này lung tung thì sẽ có khả năng dãy $b$ hiện tại chưa phải là dãy tối ưu để có thể mở rộng. Vì có thể sẽ tồn tại $b_k \geq a_{i + 1}$ thì ta sẽ không mở rộng đúng như ta quy ước được. Nếu tồn tại $a_x$ **nhỏ nhất** mà vẫn tạo được dãy $b$ độ dài $k$ này thì ta có thể **tham lam** chọn $a_x$ nhỏ nhất để có thể mở rộng dãy nhiều hơn.
- **Chứng minh 2:** Giả sử ta không thể mở rộng dãy $b$ hiện tại thêm phần tử nào, thì đồng nghĩa với việc sẽ tồn tại một phần tử trong mảng $b$ **lớn hơn hoặc bằng** $a_i$. Điều đó có nghĩa là nếu ta thay thế $b_j = a_i$ với $j$ là vị trí nhỏ nhất $b_j \geq a_i$ thì trong các giá trị $a_{i + 1}, a_{i + 2}, .... a_n$, ta sẽ có thể mở rộng thêm dãy $b$ bằng việc thay thế các giá trị **lớn** làm $b_k$ thể giảm xuống thuận lợi cho việc mở rộng dãy $b$ tối ưu hơn.

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

int longestIncreasingSubsequence(vector<int>& a){
    vector<int> b;
    int n = a.size();
    for(int i = 0; i < n; ++i){
        if(b.empty() or b.back() < a[i]) {
            //có thể mở rộng trực tiếp
            b.push_back(a[i]);
        }
        else{
            //tìm vị trí j thỏa yêu cầu
            int j = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
            b[j] = a[i];
        }
    }
    return (int)b.size();
}

:::

# Bài toán 2
## Đề bài
- Có $n$ chiếc hộp được cho trước chiều dài $d$ và chiều rộng $r$. Một hộp có thể chứa một hộp khác nhỏ hơn nó nếu chiều dài và chiều rộng của nó đều lớn hơn hộp kia. Ví dụ, chiếc hộp $a$ có thể chứa hộp $b$ nếu như chiều dài và chiều rộng của hộp $a$ đều lớn hơn $b$, tức là $d_a > d_b$ và $r_a > r_b$.
- Mỗi hộp chỉ có thể chứa một hộp duy nhất, và hộp nhỏ hơn có thể chứa các hộp nhỏ hơn nữa. Giả sử hộp $a$ chứa hộp $b$ và hộp $c$ chứa hộp $a$, lúc này ta có thể mang đi cả 3 hộp $a, b, c$ cùng lúc bằng việc chỉ mang đi hộp $c$, vì lúc này hộp $c$ đã chứa hộp $a$ và trong $a$ có hộp $b$.
- Tìm số hộp nhiều nhất ta có thể mang đi cùng lúc.
### Input
- Dòng đầu tiên gồm một số nguyên dương $n$ - số lượng hợp cho trước.
- Dòng thứ $i$ trong $n$ dòng tiếp theo gồm một cặp số nguyên dương $(d_i, r_i)$ - chiều dài và chiều rộng của từng hộp.
### Output
- Gồm một số nguyên dương là số hộp nhiều nhất có thể mang đi cùng lúc.
### Giới hạn
- $1 \le n \le 1000$
- $1 \le d_i, r_i \le 10^6$
### Sample Input

6
3 4
2 5
3 2
1 1
6 7
4 3

### Sample Output

4

### Giải thích
- Ta sẽ chọn các hộp sau theo thứ tự từ bé đến lớn: $4, 3, 1, 5$ hoặc $4, 3, 6, 5$.
## Lời giải
:::spoiler Ý tưởng
- Ta sẽ lưu $n$ hộp đã cho theo kiểu dữ liệu `pair` và sắp xếp lại bằng hàm `sort`, vì chiều dài là `first` của pair nên các hộp sẽ được sắp xếp theo chiều tăng dần của chiều dài.
- Sau khi đã sắp xếp, lúc này ta sẽ có $d_i \le d_{i+1}$ với mọi $1 \le i < n$. Vì thế hộp thứ $i$ không thể chứa hộp $j$ ($i < j \le n$) do $d_i \le d_j$, nên hộp $i$ chỉ có thể chứa các hộp trong $i-1$ hộp đầu (nếu có).
- Đến đây ta có thuật toán như sau, gọi $f[i]$ là số hộp nhiều nhất có thể mang đi cùng lúc nếu hộp có kích thước lớn nhất trong các hộp này là hộp thứ $i$. Trường hợp cơ sở sẽ là $f[i] = 1$ với mọi ($1 \le i \le n$) vì ta có thể chỉ mang 1 hộp.
- Theo nhận xét ở trên, ta chỉ có thể chứa thêm hộp nằm trong khoảng $i-1$ hộp đầu tiên, bài toán lúc này sẽ quay về bài toán tìm dãy con tăng dài nhất. Vì thế ta duyệt mọi $j$ với $1 \le j < i$, kiểm tra xem hộp $j$ có thể nằm bên trong hộp $i$ hay không, nếu có thì ta cập nhập $f[i] = f[j]+1$.
:::

:::spoiler Cài đặt

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    pair<int, int> box[n + 1];
    for (int i = 1; i <= n; i++) cin >> box[i].first >> box[i].second;
    sort(box + 1, box + n + 1);
    
    int f[n + 1], ans = 0;
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (box[i].first > box[j].first && box[i].second > box[j].second)
                f[i] = max(f[i], f[j] + 1);
        ans = max(ans, f[i]);
    }
    
    cout << ans;
    return 0;
}

:::

# Bài tập vận dụng
## [CSES - Towers](https://cses.fi/problemset/task/1073)
### Đề bài
- Cho $n$ khối lập phương có kích thước lần lượt là $k_1, k_2, k_3, ..., k_n.
- Một tòa thấp là dãy khối lập phương (có thể không liên tiếp) được chọn phải thỏa mãn các khối lập phương liền kề nhau được chọn khối ở dưới **lớn hơn** khối ở trên.
- Đếm số dãy ít nhất cần sử dụng để ghép $n$ khối lại phương lại thành các tòa tháp.
#### Input
- Dòng đầu gồm số nguyên dương $n$ là số khối lập phương ($n \leq 2 \cdot 10^5$).
- Dòng tiếp theo gồm $n$ số nguyên dương là kích thước của $n$ khối lập phương : $k_1, k_2, k_3, ..., k_n$ ($k_i \leq 10^9$).
#### Output
- Gồm $1$ số nguyên dương duy nhất là số tòa tháp ít nhất.
#### Sample Input

5
3 8 2 1 5

#### Sample Output

2

#### Giải thích
- Tòa tháp thứ nhất gồm $3$ khối lập phương có kích thước : $3 \ 2 \ 1$.
- Tòa tháp thứ hai gồm $2$ khối lập phương có kích thước : $8 \ 5$.

## WAVIO (Không có judge)
### Đề bài
- Cho dãy số nguyên gồm $n$ số nguyên $a_1, a_2, a_3, ..., a_n$. Một dãy con $b_1, b_2, b_3, ..., b_k$ của dãy $a$ được gọi là **gợn sóng** khi tồn tại vị trí $m$ sao cho $b_1 < b_2 < b_3 < ... < b_m > b_{m + 1} > b_{m + 2} > ... > b_k$. Tìm dãy **gợn sóng** có đồ dài lớn nhất là dãy con (có thể không liên tiếp) của dãy $a$.
#### Input
- Dòng đầu gồm số nguyên dương $n$ ($n \leq 10^3$).
- Dòng tiếp theo gồm $n$ số nguyên : $a_1, a_2, a_3, ..., a_n$ ($-10^9 \leq a_i \leq 10^9$).
#### Output
- Gồm $1$ số nguyên dương duy nhất là dãy **gợn sóng** dài nhất.
#### Sample Input

6
2 1 3 2 5 3 

#### Sample Output

4

#### Giải thích
- Dãy **gợn sóng** dài nhất có độ dài $4$ là $1 \ 3 \ 5 \ 3$, một dãy khác có thể là $2 \ 3 \ 5 \ 3$.

# 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.
* Tránh lạm dụng kỹ thuật này thành thói quen, hãy suy nghĩ bài toán theo nhiều cách trước rồi mới đến kỹ thuật này.
- 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, học sinh giỏi và có khả năng xuất hiện trong các kì thi như tuyển sinh 10. 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.
- Ngoài ra, Quy hoạch động thường là một kỹ thuật khá là tốn kém "bộ nhớ" lẫn thời gian (VD Có vài bài tập có công thức truy hồi 4-5 chiều hay nhiều hơn) nên việc áp dụng kỹ thuật này khá là mạo hiểm.
- Một mẹo nhỏ khi làm bài tập để xác định bài này có phải sử dụng Quy hoạch động hay không chính là **tính chất tham lam** của bài toán. Ví dụ những bài toán sử dụng có thể **tham lam** và có thể chứng minh hay cảm nhận rằng **tham lam** là chính xác thì ta sẽ dùng **tham lam** thay vì Quy hoạch động (Thường tham lam ít tốn nhiều bộ nhớ và thời gian hơn QHĐ).

# 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). |

# Kết thúc

- Để học tốt và phát triển tư duy Lập trình Thi đấu nói chung và Quy hoạch động nói riêng cần đổ rất nhiều tâm sức và thời gian đối với tin học.
- Để phát triển tốt hơn thì mọi người có thể tham khảo nhiều bài viết về cùng một chủ đề để nắm bắt được nhiều ưu điểm, nhược điểm của các chủ đề mình tìm kiếm.
- Ngoài ra, với Quy hoạch động là một kỹ thuật khá "khó tiêu" nên để làm chắc Quy hoạch động thì cần phải làm nhiều bài tập. Mọi người có thể tìm kiếm nhiều bài hơn trên các nguồn OJ / Codeforces khác chứ không nội trong bài viết tụi mình đề cập đến.
- Lời kết đến đây xin chúc mọi người nắm bắt được Kỹ thuật Quy hoạch động này nhé !