Solving the ATM problem with Dynamic Programming

The ATM problem is a popular problem in FAANG interviews. The problem requires you to find the minimum number of banknotes needed to withdraw a specified amount of money from an ATM containing banknotes of various denominations. , we solved this problem using a . However, this approach does not always guarantee an optimal solution. In the previous article greedy algorithm In this article, we will solve the problem using dynamic programming. Problem Statement Given an ATM containing banknotes of different denominations, write a function that will withdraw the specified sum of money using the minimum possible number of banknotes. The function should return an or if the sum cannot be withdrawn. N array of numbers null Dynamic Programming Dynamic programming is an approach to problem-solving that involves breaking down a problem into smaller subproblems. Typically, these subproblems differ only in their input values. A classic example is the Fibonacci sequence. Before calculating , we calculate , and so on, until we reach the subproblem , for which the answer is 1. F(N) F(N-1) F(0) When solving problems using dynamic programming, we usually store the result of each subproblem in a table. Example Let's say we have the following banknotes in an ATM: , and we want to withdraw . We can create a table to store the values of , where is the number of banknotes: [1000, 500, 100] 1100 F(N) N F(0) We can obtain only the sum of 0 using 0 banknotes: Sum Banknotes 0 [] F(1) We add a banknote of and get 2 possible combinations: 1000 Sum Banknotes 0 [] 1000 [1000] F(2) We add another banknote of to the previous table and get 2 new combinations: 500 Sum Banknotes 0 [] 1000 [1000] 500 [500] 1500 [1000, 500] F(3) We add another banknote of to the previous table and get 4 new combinations: 100 Sum Banknotes 0 [] 1000 [1000] 500 [500] 1500 [1000, 500] 100 [100] 1100 [1000, 100] 600 [500, 100] 1600 [1000, 500, 100] Result We look for the key in the table and get the answer . 1100 [1000, 100] Note that if we had obtained the same sum using different banknotes at any point in the process, we would store the result that used the fewest banknotes in the table. In our case, we consider the banknotes in decreasing order, so we prioritize the value already in the table. Thus, we obtain an optimal solution. Algorithm Create a table to store the sum and banknotes Loop , where is the number of banknotes, and for each , do the following: from 1 to N N n Create a temporary table. Copy each row from the main table, add the current banknote to it, and store it in the temporary table. Copy the values from the temporary table into the main table. If there is already a row in the main table with the same sum, give priority to the value from the temporary table. Search the table for the row with the required sum and output the answer. If there is no such row in the table, then the solution for these values is not available. Code const withdraw = (total, _coins) => { coins = [..._coins].sort((a, b) => b - a); // Main table // key - sum // value - array of banknotes let sums = {0: []}; // Iterator from 1 to N banknotes for (key in coins) { const val = coins[key]; // Banknote value const newSums = {}; // Temporary table // Iterator over elements of the main table for ([key, values] of Object.entries(sums)) { const newKey = parseInt(key) + val; // New sum newSums[newKey] = [...values, val]; // New set of banknotes } sums = { ...newSums, ...sums, // priority to the main table }; } return sums[total] || null; }; Complexity of Algorithm To solve this problem, we iterate over banknotes, and for each banknote, we iterate over elements in the main table. The maximum possible number of rows in the table is equal to the withdrawal amount, considering that we don't store values more than the required value to withdraw. N S Therefore, the time complexity of the algorithm is , where is the number of banknotes, and is the withdrawal amount. O(NS) N S Summary We learned how to use dynamic programming to solve this problem. Unlike greedy algorithms, dynamic programming can guarantee an optimal solution to the ATM problem in all cases. The time complexity of dynamic programming is , where is the number of banknotes and is the withdrawal amount. Although this complexity is relatively high, it is still better than generating all possible combinations. O(NS) N S