The problem is classic Dynamic Programming example where you need to find out the maximum amount of American Dollars you can accumulate with a Bytelandian Gold Coin of value n.
I am gonna give you the recursive equation using which you can solve the problem under the given timeconstraint.
dp[i] =
\begin{cases}
0, & \text{i = 0} \\
1, & \text{i = 1} \\
2, & \text{i = 2} \\
3, & \text{i = 3} \\
4, & \text{i = 4} \\
max(i, dp[i >> 1] + dp[i / 3] + dp[i >> 2] & \text{i > 4} \\
\end{cases}
In the above recursive equation dp[i >> 1] is equivalent to dp[i / 2] and dp[i >> 2] is equivalen to dp[i / 4].
If you want to refer to my solutions:

Byteladian Gold Coins Solution.
Thanks for reading.
Peace