DP Solution to the ATM Problem

Solution.java

import java.util.*;

public class Solution {

    public static int[] getMinimumNotesCombination(int targetAmount, int[] notes) {
        final int INF = Integer.MAX_VALUE;

        int notesCount = notes.length;
        int[][] dp = new int[targetAmount + 1][notesCount]; // represents
        // a combination of notes with minimum sum that gives you some amount

        for (int i = 1; i <= targetAmount; i++) {
            Arrays.fill(dp[i], INF); // initially the combination of notes
            // to represent some amount is all set INF
        }

        for (int amount = 1; amount <= targetAmount; amount++) {
            // the current amount we're getting the minimum notes combination for
            for (int noteIndex = 0; noteIndex < notesCount; noteIndex++) {
                for (int currentNoteSum = 0; currentNoteSum <= amount; currentNoteSum += notes[noteIndex]) { // iterates over all
                    // multiples of the current note

                    int currentNoteCount = currentNoteSum / notes[noteIndex]; // represents
                    // the number notes needed to make the current multiple

                    int previous = amount - currentNoteSum; // previous represents an amount that we
                    // computed previously that will be used to calculate the optimal result for the current amount

                    if (dp[previous][0] != INF) { // if we found a value for the previous amount
                        /**
                         * We have two options
                         * Option 1 -> add the number of notes needed to
                         * make the current multiple to the optimal solution for the previous
                         * Option 2 -> leave amount as it is
                         * Between Option 1 & 2 we will take whichever uses the minimum number of notes
                         **/

                        long previousSum = 0;
                        for (int note = 0; note < notesCount; note++) {
                            previousSum += dp[previous][note]; // minimum number of notes 
                            // we needed to create previous
                        }
                        long firstChoice = currentNoteCount + previousSum; // Option 1
                        
                        long secondChoice = 0; // secondChoice -> if we leave the amount array as it is 
                        for (int note = 0; note < notesCount; note++) {
                            secondChoice += dp[amount][note]; // Option 2
                        }

                        if (firstChoice < secondChoice) {
                            System.arraycopy(dp[previous], 0, dp[amount], 0, notesCount); // the contents of the previous
                            // array is copied to the current amount's array 
                            dp[amount][noteIndex] += currentNoteCount;
                        }
                    }
                }
            }
        }

        return dp[targetAmount]; // dp target amount will now contain the result(it will
        // contain INF if it isn't possible to get target amount using the available notes)
    }

    public static void main(String[] args) {
        int[] coins = {100, 50, 20};
        int[] result = getMinimumNotesCombination(230, coins);

        for (int value : result) {
            System.out.print(value + " ");
        }
    }
}