Có một chú robot đặt ở góc trên cùng bên trái của lưới kích thước m x n (tọa độ grid[0][0]).
Robot muốn di chuyển tới góc dưới cùng bên phải của lưới (tọa độ grid[m-1][n-1]). Ở mỗi bước, robot chỉ có thể di chuyển sang phải (Right) hoặc đi xuống dưới (Down).
Hãy tính tổng số đường đi duy nhất mà robot có thể đi để đến được đích.
Ví dụ 1:
Input:
m = 3
n = 7
Output: 28Ví dụ 2:
Input:
m = 3
n = 2
Output: 3Định Dạng Đầu Vào (Input)
Dòng 1: Số nguyên m
Dòng 2: Số nguyên n
Dòng 2: Số nguyên n
Định Dạng Đầu Ra (Output)
Một số nguyên duy nhất là số đường đi khả dĩ
Ràng Buộc (Constraints)
1 <= m, n <= 100Đáp án luôn nằm trong giới hạn số nguyên 32-bit (<= 2 * 10^9).
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
3
7
Output:
28
Giải thích: 28 đường đi
Ví dụ 2:
Input:
3
2
Output:
3
Giải thích: 3 đường đi
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Quy Hoạch Động Lưới 2D O(m * n)
Để tới ô (r, c), robot chỉ có thể đi từ ô bên trên (r-1, c) hoặc từ ô bên trái (r, c-1):
dp[r][c] = dp[r-1][c] + dp[r][c-1]
Dữ liệu đầu vào (Input):
3
7
Kết quả kỳ vọng (Expected Output):
28
Dữ liệu đầu vào (Input):
3
2
Kết quả kỳ vọng (Expected Output):
3
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
