---
title
Quy hoạch động (Phần 4) - Lời giải
---

Quy hoạch động (Phần 4) - Lời giải
===

---

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

---

# 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

## Lời giải

:::spoiler **Ý tưởng**
- $a[:i]$: xâu con của xâu $a$ gồm $i$ kí tự đầu tiên
- Gọi $dp(i,\space j)$ là số thao tác cần thực hiện ít nhất để 2 tiền tố $s[:i]$ và $t[:j]$ bằng nhau
- Công thức truy hồi của bài toán:
- Trường hợp 1: Xóa kí tự $s_i$ sẽ tốn 1 thao tác, và ta vẫn cần biến đổi xâu $s[:i-1]$ thành $t[:j]$ nên sẽ tốn $1 + dp(i-1,\space j)$ thao tác
- Trường hợp 2: Thêm kí tự $t_j$ vào cuối xâu $s$ sẽ tốn 1 thao tác, và ta vẫn cần biến đổi xâu $s[:i]$ thành $t[:j-1]$ nên sẽ tốn $1 + dp(i,\space j-1)$ thao tác
- Trường hợp 3: Thay đổi kí tự $s_i$ thành $t_j$ sẽ tốn 1 thao tác, và ta vẫn cần biến đổi xâu $s[:i-1]$ thành $t[:j-1]$ nên sẽ tốn $1 + dp(i-1,\space j-1)$ thao tác
- Trường hợp 4: $s_i = t_j$, nên ta chỉ cần biến đổi xâu $s[:i-1]$ thành $t[:j-1]$ và tốn $dp(i-1,\space j-1)$ thao tác. Đây có thể coi như là thao tác biến đổi $s_i$ thành $t_j$ nhưng không mất chi phí do 2 kí tự đã bằng nhau.
- Cập nhật $dp(i,\space j)$ bằng trường hợp tốn chi phí ít nhất
- Độ phức tạp: $O(|s| * |t|)$
:::

::: spoiler **Code mẫu**

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string s, t; cin >> s >> t;
    int n = s.size(), m = t.size();
    s = "#" + s; t = "#" + t;
    vector <vector<int>> dp(n+3, vector<int>(m+3, 0));
    for (int i = 1; i <= n; ++i) dp[i][0] = i;
    for (int i = 1; i <= m; ++i) dp[0][i] = i;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            int cost1 = dp[i-1][j] + 1;
            int cost2 = dp[i][j-1] + 1;
            int cost3 = dp[i-1][j-1] + 1;
            int cost4 = 1e10;
            if (s[i] == t[j]) cost4 = dp[i-1][j-1];
            dp[i][j] = min({cost1, cost2, cost3, cost4});
        }
    }   
    cout << dp[n][m] << "\n";
    return 0;
}

:::

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

## Lời giải

:::spoiler **Ý tưởng**
Chúng ta xử lý trường hợp khi $i$ $=$ $0$ riêng biệt. Nếu $x[0]$ $=$ $0$, ta có thể thay thế nó bằng bất cứ giá trị nào ($dp[0][v]$ $=$ $1$ cho tất cả $v$). Ngược lại, nếu $x[0]$ $=$ $v$ $\ne$ 0 , thì $dp[0][v]$ $=$ $1$ là giá trị duy nhất được phép.

Bây giờ đến các chỉ số khác $i > 0$ . Nếu $x[i]$ $=$ $0$ , chúng ta có thể thay thế nó bằng bất kỳ giá trị nào. Tuy nhiên, nếu chúng ta thay thế nó bằng $v$ , giá trị trước đó phải là $v-1$ , $v$ hoặc $v+1$ . Do đó, số cách để điền vào mảng đến $i$ là tổng của giá trị trước đó là $v-1$ , $v$ và $v+1$ . Nếu x[i] = v từ đầu vào, chỉ có $dp[i][v]$ được phép (nghĩa là $dp[i][j]$ $=$ $0$ nếu j $\ne$ v). Tuy nhiên, **$dp[i][v]$ $=$ $dp[i-1][v-1]$ $+$ $dp[i-1][v]$ $+$ $dp[i-1][v+1]$**.

Độ phức tạp là $O(n * m)$ trong trường hợp xấu nhất khi x toàn bộ là số $0$
:::

::: spoiler **Code mẫu**

#include <bits/stdc++.h>
using namespace std;

int main() {
  int mod = 1e9+7;
  int n, m;
  cin >> n >> m;
  vector<vector<int>> dp(n,vector<int>(m+1,0));
  int x0;
  cin >> x0;
  if (x0 == 0) {
    fill(dp[0].begin(), dp[0].end(), 1);
  } else {
    dp[0][x0] = 1;
  }
  for (int i = 1; i < n; i++) {
    int x;
    cin >> x;
    if (x == 0) {
      for (int j = 1; j <= m; j++) {
	for (int k : {j-1,j,j+1}) {
	  if (k >= 1 && k <= m) {
	    (dp[i][j] += dp[i-1][k]) %= mod;
	  }
	}
      }
    } else {
      for (int k : {x-1,x,x+1}) {
	if (k >= 1 && k <= m) {
	  (dp[i][x] += dp[i-1][k]) %= mod;
	}
      }
    }
  }
  int ans = 0;
  for (int j = 1; j <= m; j++) {
    (ans += dp[n-1][j]) %= mod;
  }
  cout << ans << endl;
}

:::