Đếm số đường đi trong lưới chỉ đi sang phải và xuống dưới

Mô tả bài toán

Đây là bài quy hoạch động trên lưới đầu tiên: mỗi ô trong lưới nhận đóng góp từ ô phía trên và ô bên trái, nên bảng hai chiều được điền theo thứ tự từ trên xuống dưới, từ trái sang phải. Hàng đầu và cột đầu là điều kiện đầu, vì từ đó chỉ có đúng một cách đi tới.

Yêu cầu

Cho lưới gồm n hàng và m cột. Xuất phát từ ô góc trên bên trái, mỗi bước chỉ được đi sang ô bên phải hoặc xuống ô bên dưới. Hãy đếm số đường đi khác nhau để tới ô góc dưới bên phải.

Quy ước nộp bài

Nộp tệp solution.cpp đọc n và m từ stdin và ghi kết quả ra stdout. Chỉ in một số nguyên trên một dòng, không kèm chữ hay dấu cách thừa.

Ràng buộc

• Chỉ được đi sang phải hoặc xuống dưới, không đi ngược lại và không đi chéo.
• Thời gian cho mỗi bộ dữ liệu là 1 giây.