ИЗВИНЕНИЕ, РЕБЯТА! ВИНОВАТ! Спасибо за напоминание, я выяснил, что f (0, k) == f (k, 0) == 1. Этот вопрос о том, как подсчитать количество кратчайших путей от сетки (0,0) до (m, n ).
Теперь мне нужно решить следующее уравнение, чтобы точно узнать, чему равно f (m, n).
1) f(m,n) = 0 : when (m,n) = (0,0)
**2) f(m,n) = 1 : when f(0,k) or f(k,0)**
3) f(m,n) = f(m-1,n) + f(m,n-1) : when else
например:
1) f(0,0) = 0;
2) f(0,1) = 1; f(2,0) = 1;
3) f(2,1) = f(1,1) + f(2,0) = f(0, 1) + f(1, 0) + f(2, 0) = 1 + 1 + 1 = 3
Я помню, что существует стандартный способ решения такого рода двоичных рекуррентных уравнений, который я узнал в своем классе алгоритмов несколько лет назад, но сейчас я просто не могу вспомнить.
Кто-нибудь может намекнуть? Или ключевое слово, как найти ответ?