Чтобы получить более подробную информацию об идее Нико Шертлера, вам действительно нужно вычислить значения в диагональном порядке (поскольку в формуле есть m+1).Чтобы сделать это более понятным, давайте введем еще одну функцию g, такую, что
g(k, n) = f(k-n, n)
или, иначе говоря,
f(m, n) = g(m+n, n)
А теперь давайте перепишем рекурсивную формулу для f в терминах g:
g(m+n, n) = g(m+n, n-1) + g(m+n-1, n-1) + g(m+n-2, n-1) + g(m+n-1, n)
или
g(k, n) = g(k, n-1) + g(k-1, n-1) + g(k-2, n-1) + g(k-1, n)
, и теперь вы можете видеть, что здесь и k, и n никогда не растут, поэтому вы можете вычислить g(k,n) если у вас есть только все значения для двух предыдущих строк, то есть g(k-1, i) и g(k-2, i) + предыдущие значения в текущей строке.
Если вы поместите это в код, вы можете получить что-то вроде этого:
#include <stdio.h>
int f(int m,int n)
{
if (n == 0)
return m;
if (m == 0)
return n;
return f(m+1, n-1) + f(m, n-1) + f(m-1, n-1) + f(m-1, n);
}
int f2(int m, int n) {
// covers bad cases such as m = n = 0
if (m == 0)
return n;
if (n == 0)
return m;
int buf1[m + n + 1];
int buf2[m + n + 1];
int buf3[m + n + 1];
int* curLine = buf1;
int* prevLine1 = buf2;
int* prevLine2 = buf3;
// init first two lines with f(0,0), f(1,0) and f(0,1)
prevLine1[0] = 0;
curLine[0] = 1;
curLine[1] = 1;
for (int i = 2; i <= m + n; i++) {
// cycle buffers to avoid dynamic allocation for each line
// curLine -> prevLine1 -> prevLine2 -> curLine
int* tmp = prevLine2;
prevLine2 = prevLine1;
prevLine1 = curLine;
curLine = tmp;
curLine[0] = curLine[i] = i; // f(0,i) and f(i,0)
for (int j = 1; j < i; j++) {
curLine[j] = curLine[j - 1] // m+1, n-1
+ prevLine1[j] //m-1, n
+ prevLine1[j - 1] //m, n-1
+ prevLine2[j - 1]; //m-1, n-1
}
}
return curLine[n];
}
int main()
{
for(int n = 0; n < 6; n++)
for(int m = 0; m < 6; m++) {
int fv = f(m,n);
int f2v = f2(m,n);
printf("n = %d, m = %d, f = %d f2 = %d\n", n, m, fv, f2v);
}
return 0;
}
См. онлайн-демонстрацию , показывающую, что выходные данные f и f2 одинаковы.
Обновление (более простой код)
На самом деле вам не нужно идти по диагонали.Да, есть зависимость от m+1, но для n зависимость только для n и n-1.Так что достаточно сделать внешний цикл на n (вместо m) и просто перейти во внутренний цикл до m+n-i (а не просто до m), и тогда вам понадобится только одинпредыдущая строка значений f.Код выглядит следующим образом:
int f3(int m, int n){
// covers bad cases such as m = n = 0
if (m == 0)
return n;
if (n == 0)
return m;
int buf1[m + n + 1];
int buf2[m + n + 1];
int* curLine = buf1;
int* prevLine = buf2;
// f(i, 0)
for (int i = 0; i <= m + n; i++)
curLine[i] = i;
for (int i = 1; i <= n; i++) {
// swap buffers to avoid dynamic allocation for each line
int* tmp = prevLine;
prevLine = curLine;
curLine = tmp;
curLine[0] = i; // f(0, i)
for (int j = 1; j <= n + m - i; j++) {
curLine[j] = curLine[j - 1] //m-1, n
+ prevLine[j + 1] //m+1, n-1
+ prevLine[j] //m, n-1
+ prevLine[j - 1]; //m-1, n-1
}
}
return curLine[m];
}
Обновленная демоверсия с f2 и f3 здесь здесь