# Quy hoạch động :: Part 1
***Writer**: Nguyễn Hữu Phúc*
***Reviewer**: Zeena (i2225 PTNK ĐHQG TP. HCM)*
> ~~Truyền thuyết~~ kể lại rằng, những người biết code quy hoạch động giờ đang đứng trên đỉnh xã hội, ra đường mấy em gái thấy cứ vây quanh xin chụp hình chung, chó nhìn không dám sủa, ăn có tô phở mà người xung quanh bàn tán lên xuống vì biết tôi code được quy hoạch động, họ hàng ghen tị, gia đình tự hào và tôi viết cái post này :).
### I. Cơ bản về quy hoạch động - Mở đầu
Về cơ bản thì, quy hoạch động **chỉ đơn giản là** **memoization** - kĩ thuật lưu trữ và **formula** - công thức tổng quát, không biết có đúng là vậy không nhưng trong VNOI Wiki có post thầy **Lê Minh Hoàng** nói vậy.

Tuy nhiên, dù chỉ bao gồm 2 kĩ thuật chính, quy hoạch động bao gồm các biến thể thường thấy sau đây:

> * Quy hoạch động một chiều
> * Quy hoạch động hai chiều
> * Quy hoạch động trên cây
> * Quy hoạch động chữ số
> * Quy hoạch động trạng thái
> * Quy hoạch động bao lồi
> * ...

Không chỉ đa dạng về biến thể, quy hoạch động còn đa dạng với các kĩ thuật tối ưu đi kèm như:

> * Kết hợp cấu trúc dữ liệu cây
> * Kết hợp nhân ma trận
> * Kết hợp hash map / nén số
> * ...

Nhưng các thuật toán phức tạp sẽ không được nhắc ở đây đâu vì mới chỉ là part 1 và không muốn đuổi người đọc nên chúng ta sẽ chỉ làm quen với quy hoạch động một chiều, kĩ thuật cơ bản nhất.

### II. Bài toán lát gạch, bài toán con ếch và cơ sở của Quy hoạch động
#### 1. Bài toán lát gạch
Ok, it's Fibonacci time, hầu hết các trang / kênh / blog dạy thuật toán đều bắt đầu với cái này, dù không biết các bạn như thế nào nhưng mình thấy chả ai làm thuật Fibonacci mà lại đi đệ quy kiểu đó cả, vừa phức tạp vừa chậm hơn cách dùng mảng hay lưu index. Cho nên là, ta sẽ bắt đầu với bài toán lát gạch nhé.

Có thể bạn đã biết, bài toán lát gạch đơn giản chỉ là y hệt Fibonacci, nhưng vì ở đây nó cần suy ra công thức nên mình sẽ làm.

Nếu bạn chưa biết tới bài toán này, nội dung của nó như sau:

* Cho một sàn nhà có dạng $2\times N$, tìm số cách để lát những viên gạch dạng $1\times 2$ hoặc $2\times 1$ vào sàn nhà trên sao cho không có vùng diện tích nào không được lát.

Để giải bài toán này trước hết chúng ta hãy thử xem với $N$ nhỏ, cụ thể tầm $N\leq 5$ chúng ta có thể nhận ra rằng kết quả từ $1$ tới $5$ lần lượt là $1$, $2$, $3$, $5$, $7$,$...$

Rất dễ để thấy, kết quả của bài toán nếu $N\leq 2$ sẽ là $N$ và với $N\geq 3$ sẽ là tổng của kết quả $N$ - $1$ và $N$ - $2$.

Và từ đó ta có cách làm như sau:

* Với mỗi truy vấn ta sẽ truy vấn ngược xuống truy vấn $N$ - $1$ và $N$ - $2$, nếu như $N\leq 2$ ta sẽ trả về $N$
* Sử dụng phương pháp đệ quy để giải bài toán với cách làm đã nêu trên.

Tuy nhiên, với đệ quy ta sẽ cần phải tốn khoảng O($2 ^ N$) thời gian chạy và chắc chắn sẽ sập với khoảng $N\geq 25$. Lí do của thời gian chạy khủng bố trên là vì với mỗi truy vấn nó sẽ gọi 2 hàm con cho tới khi $N\leq 2$ nên độ phức tạp sẽ là $2 ^ N$.

Chúng ta khi vẽ ra biểu đồ gọi sẽ dễ dàng nhận ra rằng có rất nhiều biến được gọi nhiều lần khác nhau, đó chính là lí do chính làm nó chạy chậm, để khắc phục ta sẽ dùng một mảng lưu kết quả cho mỗi $N$ từ đó rút gọn độ phức tạp thuật toán về $O(n)$, đây gọi là **quy hoạch động**.
#### 2. Bài toán con ếch
Để dễ hình dung hơn, ta làm quen với bài toán con ếch và bệ đá, đề bài của nó tắt như sau:

*Có một con ếch đang đứng ở bệ đá thứ nhất, nó muốn nhảy tới bệ đá thứ $n$, trong mỗi lần nhảy, nó chỉ có thể nhảy $1$ hoặc $2$ ô, có nghĩa là, khi nó ở ô thứ $x$, nó có thể nhảy tới ô thứ $x + 1$ hoặc $x + 2$, tuy nhiên, đã có $k$ bệ đá trong $n$ bệ đá bị vỡ và ếch không thể đi vào đó (đảm bảo bệ thứ $1$ và bê thứ $n$ không vỡ, hãy tính số cách đi từ bệ thứ nhất đến bệ thứ $n$ của chú ếch $modulo$ $10^9 + 7$.*

Ta có thể nhận ra, số cách để đi tới một ô nào đó chính là tổng số cách để đi tới hai ô trước nó, vì chỉ có hai ô đó mới có thể tới nó, do vậy ta nghiệm ra công thức:

$way_x = way_{x - 1} + way_{x - 2}$ $mod$ $10^9 + 7$

Tuy nhiên, công thức trên chỉ đúng với $x >= 3$, số cách đi tới các ô $0, 1, 2$ ta hoàn toàn có thể đếm được một cách đơn giản, sau đó sử dụng công thức trên và có được kết quả bài toán với độ phức tạp $O(n)$.

Dưới đây là code ví dụ:
:::spoiler Implementation

way[0] = 0;
way[1] = 1;
way[2] = 1;
for i in range 3 : n
    way[i] = (way[i - 1] + way[i - 2]) % mod;
print(way[n]);

:::
### III. Đoạn kết
Ok, part 1 của quy hoạch động tới đây thôi, cảm ơn các bạn đã đọc, hẹn các bạn vào post sau - ***Quy hoạch động :: Part 2*** với sự xuất hiện của *writer zeena* và ***Các kĩ thuật LIS rối não***.
### IV. Bài tập ví dụ
> [Atcoder Educationnal DP - A: Frog 1](https://oj.vnoi.info/problem/atcoder_dp_a)
> [Atcoder Educationnal DP - B: Frog 2](https://oj.vnoi.info/problem/atcoder_dp_b)