задача на рекуррентность

[1101ь]

Во вложении описана данная функция. Нужно написать программу, которая принимает два аргумента и выводит значение функции.Проблема в том, что программа работает медленно, и у меня проблема с пониманием как правильно использовать мемоизацию.

int fm[50];


int power(int base, int exponent){
int result = 1;
while (exponent > 0){
if(exponent%2!=0){
result = (result*base);
}
exponent/=2;
base = (base*base);
}
return result;
}

int F(int n, int i){
int f;
int fsum=0;
if (fm[f]!=0){
return fm[f];

}


if(i < n){
return i;
}else{
for(int j = 1; j <= n; j++){
f = power(-1, (j+1)) * j * F(n, i-j);
fsum+=f;
fm[n]=fsum;

}}
return fm[n];

}


int main(int argc, char *argv[]){
int n, k;
scanf("%d %d", &n, &k);
printf("%d\n",F(n, k));
return 0;
}

[New man]

Никогда не пишите так.

power(-1, (j+1))

Математики так выражают изменение знака, для компьютера проще вычислить

(j&1?1:-1)

И вообще, избегайте в программировании возведения в целую степень, особенно, если степень меньше 4. Если применяете, применяйте системную фнкцию, лучше Вы не напишете.

Так как мы вычисляем значения F как сумму меньших элементов, мы можем вычислять с меньших значений функции до верхних.

constexpr int n = 3;
int f[50] = {};
for(int i = 1; i<50;++i)
{
    if(!f[i]) // Пропускаем, если уже вычисленно
       continue;
    if(i<n)
      f[i] = i;
    else
      for(int j = 1; j<=n;++j)
          f[i]+=(j&1?1:-1)*j*f[i-j];
}