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.

In the previous article, we solved this problem using a greedy algorithm. However, this approach does not always guarantee an optimal solution.

In this article, we will solve the problem using dynamic programming.

Problem Statement

Given an ATM containing N 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 array of numbers or null if the sum cannot be withdrawn.

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 F(N), we calculate F(N-1), and so on, until we reach the subproblem F(0), for which the answer is 1.

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: [1000, 500, 100], and we want to withdraw 1100. We can create a table to store the values of F(N), where N is the number of banknotes:

F(0)

We can obtain only the sum of 0 using 0 banknotes:

F(1)

We add a banknote of 1000 and get 2 possible combinations:

F(2)

We add another banknote of 500 to the previous table and get 2 new combinations:

F(3)

We add another banknote of 100 to the previous table and get 4 new combinations:

Result

We look for the key 1100 in the table and get the answer [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

1. Create a table to store the sum and banknotes

2. Loop from 1 to N, where N is the number of banknotes, and for each n, do the following:

   1. Create a temporary table.
   2. Copy each row from the main table, add the current banknote to it, and store it in the temporary table.
   3. Copy the values from the temporary table into the main table.
   4. If there is already a row in the main table with the same sum, give priority to the value from the temporary table.

3. 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 N banknotes, and for each banknote, we iterate over S 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.

Therefore, the time complexity of the algorithm is O(NS), where N is the number of banknotes, and S is the withdrawal amount.

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 O(NS), where N is the number of banknotes and S is the withdrawal amount. Although this complexity is relatively high, it is still better than generating all possible combinations.