---
title:
Quy hoạch động (Phần 4: Quy hoạch động đường đi trên lưới)
---

Quy hoạch động (Phần 4: Quy hoạch động đường đi trên lưới)
===

---

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

---

# Kiến thức cần có
Để hiểu hơn về **Quy hoạch động đường đi trên lưới (Path on Grids)**, trước hết bạn hãy tìm hiểu:
- Kĩ thuật [Quy hoạch động](https://hackmd.io/@2SchoolGuideline/r1PSIpVcT)

# Quy hoạch động đường đi trên lưới

Ở bài viết [Quy hoạch động (Phần 1: Quy hoạch động cơ bản)](https://hackmd.io/@2SchoolGuideline/r1PSIpVcT), ta đã được tiếp cận với bài toán [VM 08 Bài 01 - Bậc thang](https://oj.vnoi.info/problem/vsteps) trong phần bài tập. Tóm tắt bài toán ngắn gọn là nó yêu cầu ta tính số cách để đi từ ô đầu tiên đến ô cuối cùng, với một số điều kiện cần phải thõa của đề bài. Vậy ta sẽ phải làm như thế nào nếu như bài toán yêu cầu phức tạp hơn, cụ thể là từ 1 chiều trở thành 2 chiều ? Ta cùng tìm hiểu thông qua bài toán sau đây:

## Bài toán 1: [Grid Paths](https://cses.fi/problemset/task/1638)

#### Đề bài
- Cho một lưới $n \times n$ ô vuông. Trong đó có một số ô trống và một số ô bẫy. Ta không được đi vào các ô bẫy.
- Tính số đường đi khác nhau để đi từ góc trên bên trái đến góc dưới bên phải của ô. Ta chỉ có thể đi sang phải hoặc đi xuống dưới.
#### Input
- Dòng đầu gồm số nguyên dương $n$ $(1 \le n \le 1000)$.
- $n$ dòng tiếp theo: mỗi dòng chứa $n$ kí tự, kí tự `.` ứng với ô trống và kí tự `#` ứng với ô bẫy.
#### Output
- Một số nguyên duy nhất là đáp án của bài toán.
- Vì đáp án có thể quá lớn, chỉ cần in ra phần dư của đáp án khi chia dư cho $10^9+7$.
#### Sample Input

4
....
.*..
...*
*...

#### Sample Output

3

## Thuật toán
- Ta có thể tính ra được đáp án bằng thuật toán [DFS](https://hackmd.io/R4QXWe6jTNmNpkjryDIH4g). Tuy nhiên, với $n = 10$ và tất cả ô đều là ô trống, đáp án là $48620$, lớn hơn rất nhiều lần so với đầu vào. Thậm chí với $n = 100$, ta không thể tính được đáp án trong thời gian cho phép.
- Lúc này ta nghĩ đến kĩ thuật quy hoạch động để tối ưu thời gian. Gọi $dp(i,\space j)$ là đáp án của bài toán khi xét hình chữ nhật con gồm $i$ hàng đầu và $j$ cột đầu của bảng. Chìa khóa của bài toán này là ta chỉ có thể đi sang phải hoặc đi xuống, tức là $dp(i, \space j)$ của lưới không phụ thuộc vào các ô ở bên phải hoặc bên dưới của nó.
- Khi đó:
- Nếu ô $(i,\space j)$ là bẫy: $dp(i,\space j) = 0$ do ta không được đi vào ô bẫy
- Nếu ô $(i,\space j)$ không phải bẫy: chúng ta sẽ có $dp(i,\space j) = dp(i-1,\space j) + dp(i,\space j-1)$. Như đã nói ở trên, vì ta chỉ có thể đi xuống dưới hoặc đi sang bên phải, điều này nghĩa là ô $(i,\space j)$ chỉ có thể đi tới từ ô $(i-1,\space j)$ hoặc ô $(i,\space j-1)$. Mà kết quả của ô $(i-1,\space j)$ và $(i,\space j-1)$ đều đã được tính trước đó nên ta sẽ lấy số đường đi để tới $(i-1,\space j)$ cộng với $(i,\space j-1)$
- Cuối cùng, đáp án bài toán sẽ là: $dp(n,\space n)$
- Độ phức tạp: $O(n^2)$
:::spoiler **Code mẫu**

#include <bits/stdc++.h>
using namespace std;
//
#define int long long
//
const int mod = 1e9 + 7;
const int maxn = 1e3 + 3;
//
char a[maxn][maxn];
int dp[maxn][maxn];
//
int32_t main() // vi define int = long long nen can su dung int32_t
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) 
    {
        for (int j = 1; j <= n; ++j) cin >> a[i][j];
    }
    if (a[1][1] != '*') dp[1][1] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (i == 1 && j == 1) continue;
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod;
            if (a[i][j] == '*') dp[i][j] = 0;
        }
    }
    cout << dp[n][n] << "\n";
    return 0;
}

:::

# Đưa bài toán về đúng dạng đường đi trên lưới

## Bài toán 2: [LCS](https://oj.vnoi.info/problem/qbstr)

#### Đề bài
- Cho 2 xâu $s, t$.
- Hãy tìm độ dài lớn nhất của 1 xâu sao cho xâu đó là xâu con của $s$ và $t$. Nói cách khác, ta có thể tạo ra xâu này từ cả 2 xâu $s$ và $t$ bằng cách xóa 1 vài kí tự bất kì ở cả 2 xâu và giữ nguyên vị trí của các kí tự đó.

#### Input
- Dòng đầu gồm 1 xâu $s$
- Dòng tiếp theo gồm 1 xâu $t$
- $|s|,\space |t| <= 10^3$

#### Output
- 1 dòng in ra độ dài lớn nhất của xâu tìm được

#### Sample Input

xabcd
yazc

#### Sample Output

2

## Thuật toán
- Bài toán này cũng có thể sử dụng dạng quy hoạch động đường đi trên lưới để giải quyết. Nhưng cái lưới là gì ? Và đường đi đó là đường đi nào ? Ta hãy cùng xem chi tiết thuật toán:
- Ta gọi $dp(i,\space j)$ là độ dài dãy con chung lớn nhất tìm được khi xét tới vị tri $i$ của xâu $s$ và vị trí $j$ của xâu $t$.
- Ta thấy rằng bài toán này giống như việc ta cần đi từ di chuyển từ ô $(0, 0)$ đến ô $(n-1,\space m-1)$ với $n,\space m$ lần lượt là độ dài xâu $s,\space t$. Độ dài của xâu con chung dài nhất giống như số lần bước chéo trên lưới. Trong bài toán này, ta có thể thực hiện ba cách để di chuyển: đi sang phải, đi xuống dưới, đi chéo xuống dưới theo hướng đường chéo chính (góc trái trên xuống góc phải dưới). Đáp án của bài toán cũng chính là số lần ta bước chéo nhiều nhất.
- Công thức truy hồi của bài toán:
- Trường hợp 1: Khi $s(i) = t(j):$ $dp(i,\space j) = dp(i-1,\space j-1) + 1$
- Trường hợp 2: Khi $s(i) \neq t(j):$ $dp(i,\space j) = max(\space dp(i-1,\space j),\space dp(i,\space j-1)\space)$
- Thuật toán ở trên có thể giải thích như sau:
- Nếu $s(i) = t(j)$ thì ta luôn cập nhật như thế vì lấy giá trị lớn nhất của $dp(i-1, j-1) + 1,\space dp(i, j-1),\space dp(i-1, j)$ là điều không cần thiết vì phương án ở ô $dp(i-1, j-1) + 1$ luôn tối ưu nhất do ta cần bước chéo nhiều nhất có thể nên việc di chuyển từ trên xuống hoặc từ trái sang không bao giờ tối ưu bằng. Điều này có thể nhận thấy được dựa vào bảng minh họa ở bên dưới.
>$dp(i-1, \space j-1) + 1 \ge max(\space dp(i-1,\space j),\space dp(i,\space j-1)\space)$
- Nếu $s(i) \neq t(j)$ thì ta sẽ lấy giá trị lớn nhất của ô bên trái là $(i,\space j-1)$ hoặc ô ở trên là $(i-1,\space j)$
- Độ phức tạp: $O(|s| * |t|)$

| $dp(i,\space j)$ | $x$ | $a$ | $b$ | $c$ | $d$ |
| ---------------- |:---:| --- | --- | --- | --- |
| $y$ | $0$ | $0$ | $0$ | $0$ | $0$ |
| $a$ | $0$ | $1$ | $1$ | $1$ | $1$ |
| $z$ | $0$ | $1$ | $1$ | $1$ | $1$ |
| $c$ | $0$ | $1$ | $1$ | $2$ | $2$ |

:::spoiler **Mở rộng bài toán**
- Bạn hãy xem thử qua bài toán [này](https://oj.vnoi.info/problem/atcoder_dp_f)
- Bài toán này nâng cao hơn bài toán vừa được giới thiệu ở trên ở chỗ ta cần phải in ra xâu dài nhất thay vì chỉ độ dài. Để làm được điều này ta cần phải thực hiện thao tác truy vết
- Công thức truy vết:
- Ta sẽ dùng 2 biến $i = n$ và $j = m$
- Gọi xâu $ans$ là xâu con chung dài nhất cần tìm
- Trường hợp 1: Khi $s(i) = t(j)$: $dp(i,\space j)$ luôn được cập nhật từ ô $(i-1,\space j-1)$ nên ta thực hiện cộng kí tự hiện tại vào xâu $ans$ và giảm giá trị của $i$ và $j$ đi $1$
- Trường hợp 2: Khi $s(i) \neq t(j)$: $dp(i,\space j)$ sẽ được cập nhật từ ô $(i-1,\space j)$ nếu $dp(i-1,\space j) >= dp(i,\space j-1)$ nên ta sẽ giảm giá trị $i$ đi $1$ và ngược lại giảm giá trị của $j$ đi $1$
- Cuối cùng thực hiện lật ngược xâu $ans$ là ta đã xong bước truy vết xâu con chung dài nhất

int i = n, j = m;
string ans = "";
while (i > 0 && j > 0)
{
    if (s[i] == t[j])
    {
        ans += s[i];
        --i, --j;
    }
    else
    {
        if (f[i-1][j] > f[i][j-1]) --i;
        else --j;
    }
}
reverse(ans.begin(), ans.end());
cout << ans << el;

:::

# Bài tập vận dụng

## A. [Edit Distance](https://cses.fi/problemset/task/1639)

#### Đề bài
- Cho 2 xâu $s, t$
- Ta có thể thực hiện 3 loại thao tác sau đây:
- Thêm 1 kí tự vô xâu
- Xóa 1 kí tự khỏi xâu
- Thay đổi một kí tự ở trong xâu
- Hãy tìm số thao tác ít nhất để làm cho xâu $s$ và xâu $t$ bằng nhau

#### Input
- Dòng đầu chứa 1 xâu có $n$ kí tự
- Dòng tiếp theo chứa 1 xâu có $m$ kí tự

#### Output
- In ra số thao tác tối thiểu cần thực hiện

#### Giới hạn
- $1 \le n,\space m \le 5000$

#### Sample Input

LOVE
MOVIE

#### Sample Output

2

#### Giải thích
- Ta sẽ thực hiện thay đổi kí tự $L$ thành $M$ và thêm kí tự $I$ vào xâu $MOVE$.

## B. [Array Description](https://cses.fi/problemset/task/1746)

#### Đề bài
- Cho 1 mảng gồm $n$ phần tử có giá trị trong khoảng $[1, m]$. Giá trị tuyệt đối của hiệu các phần tử nằm cạnh nhau tối đa là $1$ (nói cách khác là $|a_i - a_{i-1}| \le 1$ với $2 \le i \le n$)
- Mảng được cho sẽ có 1 vài phần tử chưa xác định giá trị. Hãy xác định có bao nhiêu mảng thỏa điều kiện đề bài cho.

#### Input
- Dòng đầu gồm 2 số nguyên $n$ và $m$: số phần tử của mảng và giá trị tối đa của các phần tử trong mảng.
- Dòng tiếp theo gồm $n$ số nguyên $x_1, x_2, x_3,..., x_n$: giá trị của mảng, giá trị $0$ đại diện cho phần tử chưa xác định giá trị.

#### Output
- In ra một dòng duy nhất là số mảng tìm được modulo $10^9 + 7$

#### Sample Input

3 5
2 0 2

#### Sample Output

3

#### Giải thích
- Các mảng $[2, 1, 2],\space [2, 2, 2],\space [2, 3, 2]$ là các mảng tìm được thỏa điều kiện đề bài.