Bài Toán Đường Đi Trong Lưới (Unique Paths)
Bài toán:
Cho một lưới có kích thước 3 x 3 (3 dòng, 3 cột), bạn bắt đầu từ ô ở góc trên bên trái (tọa độ (0, 0)) và muốn đi đến ô ở góc dưới bên phải (tọa độ (2, 2)). Bạn chỉ có thể di chuyển sang phải hoặc di chuyển xuống dưới.
Hỏi: Có bao nhiêu cách khác nhau để bạn di chuyển từ góc trên bên trái đến góc dưới bên phải của lưới?
Lưới:
(0, 0) -> (0, 1) -> (0, 2)
|        |        |
V        V        V
(1, 0) -> (1, 1) -> (1, 2)
|        |        |
V        V        V
(2, 0) -> (2, 1) -> (2, 2)
Gợi ý:
Bạn chỉ có thể di chuyển sang phải hoặc xuống dưới, và bạn cần tính tổng số đường đi có thể có từ góc trên bên trái đến góc dưới bên phải.
Hãy dùng quy hoạch động (Dynamic Programming) để tính số cách.
Mỗi ô trong lưới có thể được tính là tổng số cách di chuyển đến đó từ ô bên trên và ô bên trái.
Bạn có thể sử dụng một bảng 2D để lưu trữ kết quả cho từng ô.
Phương pháp:
1. Khởi tạo một mảng 2D dp[3][3] để lưu trữ số cách di chuyển đến mỗi ô.
2. Mỗi ô dp[i][j] sẽ được tính bằng tổng số cách di chuyển từ ô phía trên (nếu có) và ô phía bên trái (nếu có).
3. Điều kiện biên: dp[0][0] = 1, vì đây là điểm bắt đầu.