Top-Down Approach to Dynamic Programming

Unraveling the Power of Memoization for Efficient Problem Solving

The top-down approach starts with the main problem and divides it into smaller, simpler parts. It saves the solutions to these smaller parts in a structure like a list or a table for easy access later on. This process is known as memoization. It “remembers” the answers to the smaller parts so that we don’t have to solve them again, making the whole process more efficient.

Examples of the Top-Down Approach to Dynamic Programming

Fibonacci sequence problem

Consider the problem of finding the nth number in the Fibonacci sequence. The Fibonacci sequence is defined as follows:

F(0) = 0

F(1) = 1

F(n) = F(n-1) + F(n-2) for n > 1

A naive recursive implementation would recalculate the same subproblems multiple times, leading to an exponential time complexity. Using dynamic programming with a top-down approach (memoization), we can store the results of the subproblems in a cache (dictionary or hash table) and reuse them to avoid redundant calculations. Here’s an easy-to-understand example in Ruby and Javascript:

Here is a Ruby example:

def fib(n, memo = {})
  return n if n == 0 || n == 1

  if !memo.key?(n)
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
  end

  memo[n]
end

# Example usage:
puts fib(10) # Output: 55

Here is the same code in Javascript:

function fib(n, memo = {}) {
  if (n === 0 || n === 1) {
    return n;
  }

  if (!memo.hasOwnProperty(n)) {
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  }

  return memo[n];
}

// Example usage:
console.log(fib(10)); // Output: 55

In this example, we define a function fib that takes the desired index n and an optional dictionary memo to store the computed Fibonacci numbers. When the function is called for the first time, the memo is empty. The function then checks if the result for the current input n is already in the memo. If it's not, the function calculates the result recursively and stores it in the memo before returning it.

This way, when the function is called with the same input n again, it directly returns the result from the memo without recalculating it. This approach significantly reduces the time complexity of the algorithm, making it more efficient.

Finding the minimum number of coins needed to make change for a given amount

Let’s consider the problem of finding the minimum number of coins needed to make change for a given amount. We are given an array of coin denominations and an amount. The goal is to find the smallest number of coins that add up to the target amount. Using a top-down dynamic programming approach with memoization, we can improve the efficiency of our solution.

Here is an example of top-down dynamic programming (memoization) for the minimum number of coins needed to make change for a given amount in ES6 (JavaScript) and Ruby.

In Ruby:

def min_coins(amount, coins, memo = {})
  return 0 if amount == 0
  return Float::INFINITY if amount < 0

  # Check if the result is already in the memo
  return memo[amount] if memo.key?(amount)

  # Calculate the result by trying each coin and store it in the memo
  min_num_coins = Float::INFINITY
  coins.each do |coin|
    num_coins = 1 + min_coins(amount - coin, coins, memo)
    min_num_coins = [min_num_coins, num_coins].min
  end

  memo[amount] = min_num_coins

  min_num_coins
end

# Example usage:
coins = [1, 5, 10, 25]
amount = 32
puts min_coins(amount, coins) # Output: 4 (25 + 5 + 1 + 1)

In Javascript:

function minCoins(amount, coins, memo = {}) {
  // Base cases
  if (amount === 0) {
    return 0;
  }
  if (amount < 0) {
    return Infinity;
  }

  // Check if the result is already in the memo
  if (memo.hasOwnProperty(amount)) {
    return memo[amount];
  }

  // Calculate the result by trying each coin and store it in the memo
  let minNumCoins = Infinity;
  for (let coin of coins) {
    let numCoins = 1 + minCoins(amount - coin, coins, memo);
    minNumCoins = Math.min(minNumCoins, numCoins);
  }

  memo[amount] = minNumCoins;

  return minNumCoins;
}

// Example usage:
const coins = [1, 5, 10, 25];
const amount = 32;
console.log(minCoins(amount, coins)); // Output: 4 (25 + 5 + 1 + 1)

In this example, we define a function min_coins that takes the target amount, the available coins, and an optional dictionary memo to store the minimum number of coins required for each amount. When the function is called for the first time, the memo is empty. The function then checks if the result for the current amount is already in the memo. If it's not, the function calculates the result recursively and stores it in the memo before returning it.

By using memoization, we avoid recalculating the minimum number of coins needed for the same amount multiple times, making the algorithm more efficient.