Đếm Đường Đi Với Tối Đa K Lần Rẽ

Dynamic Programming
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Trên lưới $N \times M$, bạn xuất phát tại $(1, 1)$ và đi tới $(N, M)$, mỗi bước chỉ được đi sang phải hoặc xuống dưới. Một đường đi được gọi là hợp lệ nếu số lần đổi hướng (từ đi phải sang đi xuống hoặc ngược lại) không vượt quá $K$. Hãy đếm số đường đi hợp lệ theo modulo $10^9 + 7$.

Dữ liệu vào
  • Một dòng duy nhất chứa ba số nguyên $N, M, K$ $(1 \le N, M \le 200, 0 \le K \le 200)$.
Dữ liệu ra
  • In ra số đường đi hợp lệ theo modulo $10^9 + 7$.
Ví dụ
Input Output
3 3 1 2
3 3 2 4
Giới hạn
  • $1 \le N, M \le 200$
  • $0 \le K \le 200$
  • Thời gian: 1 giây
  • Bộ nhớ: 256 MB
Draft saved