Ý tưởng chính của bài toán là sử dụng mô hình quy hoạch động trên DAG (đồ thị có hướng không chu trình) giống với bài [Đường đi dài nhất](https://marisaoj.com/problem/289) nhưng được điều chỉnh lại.
Cụ thể trong bài này ta định nghĩa hàm quy hoạch động $dp[i][j]$ là số lượng chữ cái $j$ lớn nhất trong đường đi bất kỳ kết thúc tại $i$.
*Trường hợp cơ sở.* $dp[i][j] = 1$ nếu chữ cái ở đỉnh $i$ là $j$, và $dp[i][j] = 0$ trong trường hợp ngược lại.
Từ đó ta suy ra công thức chuyển trạng thái qua mỗi cạnh $(u, v)$:
$$dp[v][j] = \max_{\text{cạnh }(u, v)\text{ tồn tại}} \left(dp[u] + (s[v] == j)\right)$$
Thứ tự tính toán được thực hiện theo thứ tự tô-pô, việc tìm thứ tự tô-pô có thể thực hiện bằng DFS hoặc thuật toán Kahn (dựa trên BFS):
```cpp
for (int u : topo) {
for (int v : adj[u]) {
for (int i = 0; i < 26; ++i) {
if (i == (s[v] - 'a')) dp[v][i] = max(dp[v][i], dp[u][i] + 1);
else dp[v][i] = max(dp[v][i], dp[u][i]);
}
}
}
```
Đáp số của bài toán chính là giá trị lớn nhất của mảng $dp$.
Độ phức tạp tính toán:
- Sắp xếp tô-pô: $O(n + m)$
- Tính mảng $dp$: $O(26 \times m)$
chithanhnguyen
Created at
2 likes