В чем проблема моего решения байтландской проблемы золотых монет CodeChef?

Question

Мое решение истекло. Кто-то может указать причину? Ссылка на проблему: https://www.codechef.com/problems/COINS

#include<iostream>
using namespace std;
static  long long int s=0;
int coin(long long int n)
{

    if(n<=11)
    {
        s=s+n;
        return n;
    }
coin(n/2)
coin(n/3)
coin(n/4);

}
int main() 
{ 

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long int  x,y;

 while(cin>>x)
 {
    coin(x);
    printf("%lld\n",s);
    s=0;

 }
} 

Answer 1

Используя подход, описанный выше, вы будете снова и снова пересчитывать одни и те же числа. map, который вы упомянули в комментариях, - это метод, называемый memoization , в этом методе вы кэшируете свои результаты и т. Д. Для каждого номера перед рекурсивным вызовом с coin(x) вы сначала проверяете, уже в таблице напоминаний, и если это так, вы можете сразу же вернуть результат, не пересчитывая его снова и снова.

Удачи!