ByteLandian challenge from CodeChef I am trying to go through the problems on CodeChef and came across this problem:


  In Byteland they have a very strange monetary system. Each Bytelandian
  gold coin has an integer number written on it. A coin n can be
  exchanged in a bank into three coins: n/2, n/3 and n/4. But these
  numbers are all rounded down (the banks have to make a profit). You
  can also sell Bytelandian coins for American dollars. The exchange
  rate is 1:1. But you can not buy Bytelandian coins. You have one gold
  coin. What is the maximum amount of American dollars you can get for
  it?


I approached it using the following algorithm:


Check if the total amount on gold coin is greater than (Total/2)+(Total/3)+(Total/4), return total amount on gold coin.
Otherwise, recursively evaluate the maximum total amounts for (Total/2),(Total/3) and (Total/4) and return the sum total of these maximums.


My attempt:

public class ByteLandGold{

public static void main(String[] args){
        System.out.println("Printing the bytelandian equivalent for:");
        int byteLandCoin = Integer.parseInt(args[0]);
        System.out.println(ByteLandianConversion(byteLandCoin));
}


private static int ByteLandianConversion(int goldCoinAmount){
        int halfValue = (goldCoinAmount/2);
        int thirdValue = (goldCoinAmount/3);
        int fourthValue = (goldCoinAmount/4);


        int totalIntermediate = halfValue + thirdValue + fourthValue;
        if(goldCoinAmount &gt; totalIntermediate)
                return goldCoinAmount;
        else{
                int maxHalfPortion = ByteLandianConversion(halfValue);
                int maxThirdPortion = ByteLandianConversion(thirdValue);
                int maxFourthPortion = ByteLandianConversion(fourthValue);
                return maxHalfPortion+maxThirdPortion+maxFourthPortion;
        }
}
}


One thing that I see in my code is that the recursive steps are calculating the overlapping sub-problems repeatedly. What would be one way to ensure that doesn't happen? Can somebody go through my code and give me some pointers on how to optimize it further and what can I change this snippet to solve it in a better way?
If you don't want to recompute the overlapping sub-problems, you could use a cache.

Create the cache in your class:

private HashMap&lt;int, int&gt; resultCache = new HashMap&lt;int, int&gt;();


Then check it at the top of the function:

if (resultCache.contains(goldCoinAmount)) return resultCache.get(goldCoinAmount);


And before returning a result, cache it:

if(goldCoinAmount &gt; totalIntermediate)
    resultCache.put(goldCoinAmount, goldCoinAmount);
    return goldCoinAmount;
else{
    int maxHalfPortion = ByteLandianConversion(halfValue);
    int maxThirdPortion = ByteLandianConversion(thirdValue);
    int maxFourthPortion = ByteLandianConversion(fourthValue);

    int result = maxHalfPortion+maxThirdPortion+maxFourthPortion;
    resultCache.put(goldCoinAmount, result);
    return result;
}


Otherwise, your code is really fairly straightforward and thus fairly readable/maintainable. Readability is far more important than raw performance most of the time.