Cho một mảng kích thước n x m. Bắt đầu tại vị trí (1, 1) con kiến chỉ có thể đi xuống hoặc đi ngang sang phải. Hỏi để đến vị trí n x m có bao nhiêu cách đi?
INPUT : Hai số nguyên dương n,m.
OUTPUT: In ra số cách đi.
|
1 |
1 |
1 |
1 |
|
1
|
2 |
3 |
4
|
|
1 |
3 |
6 |
10 |
Công thức đệ quy như sau:
Tại vị trí i, j sẽ bằng số cách đi tổng i, j-1 và i-1, j
Tại i hoặc j = 0 thì số cách đi là 1.
Đến khi nào i=j=1 thì dừng lại.(Mỏ neo)
Để tối ưu:
Ta dùng mảng 2 chiều đi lưu lại đường đi của nó.