Bài 6. Đếm số đường đi trên lưới

Mô tả

Cho một lưới kích thước n x m.

Bạn xuất phát từ ô (1,1) và cần đi tới ô (n,m). Mỗi bước bạn chỉ được phép:

• đi sang phải
• hoặc đi xuống dưới

Hãy đếm số đường đi khác nhau từ ô đầu đến ô cuối. Vì kết quả có thể rất lớn, hãy in ra theo modulo 1000000007.

Input

Gồm một dòng chứa hai số nguyên n và m.

Output

In ra số đường đi khác nhau từ (1,1) đến (n,m) theo modulo 1000000007.

Giới hạn

• 1 <= n, m <= 2000

Subtask

• Subtask 1 (20%): 1 <= n, m <= 10
• Subtask 2 (30%): 1 <= n, m <= 100
• Subtask 3 (50%): 1 <= n, m <= 2000

Hướng dẫn giải

Gọi dp[i][j] là số đường đi từ ô (1,1) đến ô (i,j).

Nhận xét

Để tới ô (i,j), bước cuối cùng chỉ có thể đến từ:

• ô phía trên (i-1,j)
• hoặc ô bên trái (i,j-1)

Vì vậy:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Lấy modulo 1000000007 sau mỗi lần cộng.

Khởi tạo

• dp[1][1] = 1
• Hàng đầu tiên chỉ có đúng 1 cách đi: đi toàn sang phải
• Cột đầu tiên cũng chỉ có đúng 1 cách đi: đi toàn xuống dưới

Thứ tự tính

Duyệt i từ 1..n, với mỗi i duyệt j từ 1..m.

Độ phức tạp

• Thời gian: O(n*m)
• Bộ nhớ: O(n*m)

Có thể tối ưu bộ nhớ xuống O(m) nếu chỉ lưu một hàng DP.

Ví dụ

Input

3 4

Output

10

Giải thích ví dụ

Từ (1,1) đến (3,4) bạn cần đi:

• 2 bước xuống
• 3 bước sang phải

Tổng cộng có 5 bước, và chỉ cần chọn vị trí cho 2 bước xuống (hoặc 3 bước sang phải), nên có:

C(5,2) = 10

đường đi.