I am trying to obtain a solution for this question https://www.spoj.com/problems/COINS/.

But oddly enough, my iterative solution:

`#include <iostream> using namespace std; int main() { int n; while(cin >> n){ long long int dp[n+2]; dp[0]=0; for(long long int i=1; i<=n; i++) dp[i]=max(dp[i/2]+dp[i/3]+dp[i/4], i); cout << dp[n] <<endl; } return 0; } `

gets a TLE, while the recursive solution for this(Not mine) gets accepted in no time:

`#include <cstdio> #include <map> #include <algorithm> using namespace std; map<int, long long> dp; long long f(int n){ if(n==0) return 0; if(dp[n]!=0) return dp[n]; long long aux=f(n/2)+f(n/3)+f(n/4); if(aux>n) dp[n]=aux; else dp[n]=n; return dp[n]; } int main(){ int n; while(scanf("%d",&n)==1) printf("%lld\n",f(n)); return 0; } `

Shouldn’t it be the opposite? I am genuinely confused. Please tell me how I can improve the first code.