1. Phân tích bài toán
- Yêu cầu: Đếm số cách di chuyển từ ô đến .
- Quy tắc di chuyển: Chỉ được đi sang phải hoặc xuống dưới.
- Ràng buộc: Không được đi vào ô có vật cản (
#). Vì kết quả rất lớn nên cần lấy dư cho . - Nhận xét: Số cách để đến ô phụ thuộc trực tiếp vào số cách đã đến các ô trước đó (ô bên trái và ô phía trên). Đây là dấu hiệu điển hình của bài toán Quy hoạch động.
2. Ý tưởng thuật toán
Sử dụng một bảng phương án , trong đó lưu trữ số cách đi từ ô đến ô .
- Trạng thái: là số cách đến ô ở hàng , cột .
- Trường hợp cơ sở: (có 1 cách duy nhất để bắt đầu tại điểm xuất phát).
- Công thức truy hồi:
- Nếu ô là vật cản (
#): . - Nếu ô là ô trống (
.):(Trong đó là số cách đi từ phía trên xuống và là số cách đi từ bên trái sang).
- Nếu ô là vật cản (
3. Các bước thực hiện
- Khởi tạo mảng 2 chiều kích thước với tất cả giá trị bằng 0.
- Đặt .
- Sử dụng hai vòng lặp lồng nhau để duyệt qua từng ô của lưới từ hàng 1 đến và cột 1 đến :
- Nếu là ô , bỏ qua (vì đã khởi tạo).
- Nếu ô hiện tại là
#, đặt . - Nếu ô hiện tại là
., tính bằng tổng của ô phía trên và ô bên trái. - Lưu ý: Luôn thực hiện phép chia lấy dư
% (10^9 + 7)sau mỗi phép cộng để tránh tràn số.
- Kết quả cuối cùng nằm tại .
4. Lưu ý khi triển khai
- Xử lý biên: Khi tính , nếu thì không có ô phía trên, nếu thì không có ô bên trái. Bạn có thể khởi tạo mảng dư ra 1 hàng và 1 cột (chỉ số 0) toàn số 0 để tránh phải kiểm tra điều kiện biên trong vòng lặp.
- Kiểu dữ liệu: Trong C++, nên dùng kiểu
long longcho mảng để tránh tràn số tạm thời khi cộng hai giá trị trước khi lấy dư. - Độ phức tạp:
- Thời gian: (khoảng phép tính, hoàn toàn đáp ứng thời gian 1s).
- Không gian: để lưu bảng DP.