Найдите формулу этого двоичного рекуррентного уравнения? f (m, n) = f (m-1, n) + f (m, n-1)

ИЗВИНЕНИЕ, РЕБЯТА! ВИНОВАТ! Спасибо за напоминание, я выяснил, что 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  

Я помню, что существует стандартный способ решения такого рода двоичных рекуррентных уравнений, который я узнал в своем классе алгоритмов несколько лет назад, но сейчас я просто не могу вспомнить.

Кто-нибудь может намекнуть? Или ключевое слово, как найти ответ?

10
задан Daniel Fischer 27 January 2012 в 13:18
поделиться