Số cách để di chuyển từ ô **(i, j)** đến ô **(x, y)** là $ \binom{x-i+y-j}{x-i} $.
**Giải thích:** để đi từ ô **(i, j)** đến ô **(x, y)** sẽ có **x-i+y-j** lần di chuyển bao gồm **x-i** lần di chuyển dọc và **y-j** lần di chuyển ngang. Trong các vị trí ấy, ta cần chọn ra **x-i** vị trí để di chuyển dọc, còn lại là di chuyển ngang. Từ đó ta có công thức trên.
Vì **n, m** lớn nên không thể quy hoạch động $O(n \times m)$ như bình thường được, ta thấy số ô chướng ngại vật nhỏ nên có ý tưởng sau:
Gọi **dp(i)** là số cách để đi từ ô **(1, 1)** đến ô chướng ngại vật thứ **i** mà không đi qua bất cứ chướng ngại vật nào ngoài chướng ngại vật thứ **i**. Ta có thể tính **dp(i)** bằng cách lấy tổng số cách đi đến được chướng ngại vật thứ **i** trừ đi số cách đi đến chướng ngại vật thứ **i** trong đó đi qua ít nhất **1** chướng ngại vật khác ngoài **i**, hay ta có:
$$ dp(i) = \binom{x_i+y_j-2}{x_i-1} - \sum_{j \neq i : \ x_j <= x_i, \ y_j <= y_i} dp(j) \times \binom{x_i-x_j+y_i-y_j}{x_i-x_j} $$
Để có được đáp án bài toán, ta chỉ cần thêm một chướng ngại vật ở ô **(n, m)** và kết quả sẽ là $dp(k+1)$.
$ \binom{n}{k} $ có thể làm trong $O(1)$ nếu tính toán trước. Độ phức tạp của bài toán: $O(k^2)$.
hungtien2202
Created at
0 likes