I made an algorithm to train my skill in dynamic programming and I would like to have feed back on it. This algorithm takes a money system (int) and have a certain amount of money to render.

Do you see any problems in this code?

public static int wayToRenderMemo(int[] array, int i, double cost, HashMap memo) {
    if(i>=array.length) {
        return 0;
    else if(cost < 0) {
        return 0;
    else if(cost == 0) {
        return 1;
    else if(memo.containsKey(String.valueOf(i)+":"+String.valueOf(cost))) {
        return (int) memo.get(String.valueOf(i)+":"+String.valueOf(cost));
    else {
        int res = 0;
        for(int j = 0; j < array.length; j++) {
            res += wayToRenderMemo(array, i+j, cost-array[j], memo);
        memo.put(String.valueOf(i)+":"+String.valueOf(cost), res);
        return res;

public static void main(String []args) {
    int[] array = {1, 2, 5, 10, 20, 50, 100};

    double amountOfMoneyToRender = 20;
    System.out.println("Number of way to render "+amountOfMoneyToRender+"€ with the following system : "+Arrays.toString(array));
    HashMap memo = new HashMap();
    long t3 = System.currentTimeMillis();
    System.out.println(wayToRenderMemo(array, 0, amountOfMoneyToRender, memo));
    long t4 = System.currentTimeMillis();
    double time2 = (t4-t3)/1000.0;
    System.out.println("Result found in : "+time2+"seconds");
  • \$\begingroup\$ Welcome to Code Review! I find it highly commendable to explicitly state the purpose of coding something, especially with practice code. 2¢: do so in the code. \$\endgroup\$ – greybeard Dec 22 '18 at 7:08
  1. Java 1.5 was released in 2004, use generics for collections.
  2. Consider making array (terrible variable name BTW) and memo fields of object that does the computation instead of passing them as arguments every time
  3. Why is amountOfMoneyToRender a double instead of int or long?
  4. String.valueOf is unnecessary for i + "some literal"
  5. Instead of using containsKey + get just do get and check for null.
  6. It might be good idea to change loop into for(int j = i; j < array.length; j++), it will make easier to spot bug in your code (with amountOfMoneyToRender=10, the result should be 11, not 100)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.