---
title{[QUY HOẠCH ĐỘNG CƠ BẢN] - Lý thuyết}
---

[QUY HOẠCH ĐỘNG CƠ BẢN] - Lý thuyết
===

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

-----

# I. Quy hoạch động:
- Giả sử, ta có bài toán sau:
>Cho [dãy Fibonacci](https://vi.wikipedia.org/wiki/D%C3%A3y_Fibonacci), tìm phần dư khi chia số Fibonacci thứ $n$ cho $10^9+7\ (n \leq 10^5)$
## Phương pháp đệ quy
- Gọi $f[i]$ là số Fibonacci thứ $i$.
- Theo quy tắc của dãy Fibonacci, để tính được $f[n]$ ta cần tính được $f[n-1]$ và $f[n-2]$. Tương tự, để tính $f[n-1]$, ta cần tính $f[n-2]$, $f[n-3] \ ...$
- Với ý tưởng trên, ta có thể giải bài toán như sau:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 1;
const int mod = 1e9 + 7;

// Tìm số Fibonacci thứ n
ll Fibo(int n) {
  // Hai số đầu của dãy Fibonacci
  if (n == 0) return 0;
  if (n == 1) return 1;
  // Công thức đệ quy
  return (Fibo(n - 1) + Fibo(n - 2)) % mod;
}

int main() {
  int n;
  cin >> n;
  // Số Fibonacci thứ n
  cout << Fibo(n);
  return 0;
}

- Ta có thể dễ dàng nhận thấy, thuật toán chậm do một số hàm $Fibo(i)$ bị lặp nhiều lần một cách không cần thiết.
- Giả sử ta cần tính $Fibo(2023)$. Lúc này, ta cần tính $Fibo(2022)$ và $Fibo(2021)$.
- Khi gọi $Fibo(2022)$, ta cần tính $Fibo(2021)$ và $Fibo(2020)$.
- Tương tự, khi ta gọi $Fibo(2021)$, ta cần tính $Fibo(2020)$ và $Fibo(2019)$.
- Ta có thể biểu diễn các hàm như sau:
- Dễ thấy rằng, khi gọi hàm $Fibo(2023)$:
- Hàm $Fibo(2021)$ bị lặp $2$ lần.
- Hàm $Fibo(2020)$ bị lặp $3$ lần.
- $\dots$
- Từ đây, ta thấy rằng bài toán không tối ưu vì có độ phức tạp lũy thừa, chỉ áp dụng được với $n$ nhỏ.
- Ta có thể tối ưu bài toán bằng cách lưu các số Fibonacci đã được tính bằng các hàm $Fibo$ khác vào mảng $f$:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 1;
const int mod = 1e9 + 7;
ll f[N];

// Tính số Fibonacci thứ n
ll Fibo(int n) {
  // Hai số Fibonacci đầu
  if (n == 0) return 0;
  if (n == 1) return 1;
  // Nếu f[n] đã được tính
  if (f[n] != 0) return f[n];
  // Công thức đệ quy
  return (Fibo(n - 1) + Fibo(n - 2)) % mod;
}

int main() {
  int n;
  cin >> n;
  // Số Fibonacci thứ n
  cout << Fibo(n);
  return 0;
}

- Độ phức tạp: $O(n)$.
- Kĩ thuật trên đi vào _bài toán lớn_ **trước** khi đi vào các _bài toán con_. Kĩ thuật này còn được gọi là **Đệ quy có nhớ**. Đây là một cách **Quy hoạch động**
- Tuy nhiên, ở bài viết này, ta sẽ tìm hiểu việc **Quy hoạch động** bằng cách tiếp cận đáp án của các _bài toán con_ **trước** khi đi tới _bài toán lớn_.

## Vậy, Quy hoạch động là gì?
- Quy hoạch động (QHĐ) - hay còn được gọi là Dynamic Programming (DP), là thuật toán giúp ta tìm được kết quả của bài toán có đầu vào cho trước bằng cách sử dụng các bài toán con tương tự nhưng có đầu vào nhỏ hơn. Khi ta giải được những bài toán nhỏ, ta có thể sử dụng QHĐ để tính ra kết quả cuối cùng.
- Quy hoạch động có $2$ phương pháp tiếp cận:
- Dùng **Đệ quy có nhớ** (DP top down).
- Khử đệ quy (DP bottom up).
- Ở phần trên, ta đã tìm hiểu một phần về **Quy hoạch động** dùng **Đệ quy có nhớ**, tiếp theo, ta sẽ tìm hiểu về cách _Khử đệ quy_.

## Các bước Quy hoạch động:
### 1. Tìm trạng thái của bài toán:
- Trạng thái là một trường hợp, là bài toán nhỏ cần giải để giải được bài toán lớn.
- Ví dụ: trạng thái trong bài tập trên là số Fibonacci thứ $n$.
### 2. Tìm mối liên kết giữa các trạng thái:
- Đây là bước quan trọng trong QHĐ: tìm liên hệ giữa các trạng thái.
- Gọi $f[i]$ là số Fibonacci thứ $i$:
$\begin{cases}
f[0] = 0 \\
f[1] = 1 \\
f[i] = (f[i-1] + f[i-2]) \mod \ 10^9 + 7, \ \ \ 2 \leq i \leq n \
\end{cases}$
- Ở công thức trên, có $2$ yếu tố cần lưu ý:
- $f[0] = 0, f[1] = 1$ là những giá trị có thể được cung cấp sẵn hoặc ta phải tự tìm, đây còn gọi là **bài toán cơ sở**.
- $f[i] = (f[i-1] + f[i-2]) \mod 10^9 + 7$ là công thức để liên hệ các trạng thái - ở đây là những tổng đã tính, hay còn gọi là **công thức truy hồi**.
- **Công thức truy hồi** là một công thức để liên hệ bài toán lớn đến các bài toán nhỏ, từ đó tìm được kết quả của bài toán ban đầu. **Công thức truy hồi** đóng vai trò rất quan trọng với những bài mang tính chất _đệ quy_ như **Quy hoạch động**.
###### Lưu ý: Vì tính quan trọng của **công thức truy hồi**, khi vào phòng thi, để chắc chắn có được số điểm của một bài **Quy hoạch động**, các bạn nên có một hàm dùng để **vét** kết quả trước khi đưa **công thức truy hồi** cho những trường hợp mà hàm **vét** bị _quá thời gian_.
### 3. Mối liên kết giữa trạng thái và kết quả của bài toán:
- Khi đã có được kết quả của bài toán con, cùng công thức truy hồi, ta có thể dễ dàng tính được $f[n]$.
### Code mẫu:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 1;
const int mod = 1e9 + 7;
ll f[N];

// Tính số Fibonacci thứ n
ll Fibo(int n) {
  // Hai số Fibonacci đầu
  f[0] = 0, f[1] = 1;
  for (int i = 2; i <= n; ++i)
    // Công thức truy hồi
    f[i] = (f[i - 1] + f[i - 2]) % mod;
  return f[n];
}

int main() {
  int n;
  cin >> n;
  // Số Fibonacci thứ n
  cout << Fibo(n);
  return 0;
}

- Độ phức tạp: $O(n)$.

## Ví dụ 1:
### Đề bài:
Cho một bảng có $n$ x $n$ ô. Một vài ô trên bảng có chứa chướng ngại vật.
Hãy tính số đường đi có thể để di chuyển từ ô góc trên bên trái tới ô góc dưới bên phải mà không đi vào ô có chướng ngại vật. Chỉ có thể di chuyển từ ô này qua ô khác bằng cách đi xuống hoặc qua phải.
#### Input
- Dòng đầu chứa số nguyên $n$: kích thước của bảng.
- $n$ dòng tiếp theo thể hiện bảng. Mỗi dòng chứa $n$ ký tự: . thể hiện một ô trống; * thể hiện một ô có chướng ngại vật.
#### Output
- Một số nguyên là số cách di chuyển mod $10^9 + 7$.
#### Ví dụ
Input:
4
....
.*..
...*
*...

Output:
3

### Lời giải
- Gọi bảng $dp[i][j]$ là số cách đi đến ô $(i, j)$.
- Công thức truy hồi cho bài toán:
$\begin{cases}
dp[i][0] = 0,\ \ 0 \leq i \leq n \\
dp[0][j] = 0,\ \ 0 \leq j \leq n \\
dp[i][j] = 0,\ \ A[i][j]\ =\ '*' \\
dp[i][j] = dp[i-1][j] + dp[i][j-1], \ \ A[i][j]\ = \ '\ .\ '
\end{cases}$
- Trường hợp $A[i][j]\ =\ '*'$ thì không thể đi đến ô $(i, j)$ nên $dp[i][j]=0$.
- Trường hợp $A[i][j]\ = \ '.'$ thì số cách đi đến ô $(i, j)$ sẽ là tổng số cách đi đến ô $(i - 1,j)$ và $(i,j - 1)$ vì chỉ có thể di chuyển xuống hoặc qua phải nên chỉ có thể đi đến một vị trí từ $2$ hướng phía trên hoặc bên trái.
### Code mẫu

#include <bits/stdc++.h>
 
using namespace std;
 
const int mod = 1e9 + 7;
string A[1001];
int dp[1001][1001];
 
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> A[i];
    // Ô đầu tiên chỉ có 1 cách đi
    dp[1][1] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            // Công thức truy hồi
            if(A[i - 1][j - 1] == '*')
                dp[i][j] = 0;
            if(i == 1 && j == 1)
                continue;
            if(A[i - 1][j - 1] != '*')
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
        }
    }
    cout << dp[n][n];
 
    return 0;
}

# II. Bài tập:
### Bài 1: [Xếp hàng mua vé](https://oj.vnoi.info/problem/nktick)
### Bài 2: [Chia trang](https://vinhdinhcoder.net/Problem/Details/5048)
### Bài 3: [Đường đi có tổng lớn nhất](https://oj.vnoi.info/problem/qbmax)
### Bài 4: [Rectangle cutting](https://cses.fi/problemset/task/1744)

# Tham khảo:
[Quy hoạch động cơ bản (Phần 1)](https://vnoi.info/wiki/algo/dp/basic-dynamic-programming-1.md)