Раскрывая силу мемоизации для эффективного решения проблем

Подход «сверху вниз» начинается с основной проблемы и делит ее на более мелкие и простые части. Он сохраняет решения для этих более мелких частей в виде списка или таблицы для быстрого доступа в дальнейшем. Этот процесс известен как мемоизация. Он «запоминает» ответы на более мелкие части, чтобы нам не приходилось решать их снова, что делает весь процесс более эффективным.

Примеры нисходящего подхода к динамическому программированию

Задача последовательности Фибоначчи

Рассмотрим задачу нахождения n-го числа в последовательности Фибоначчи. Последовательность Фибоначчи определяется следующим образом:

F(0) = 0

F(1) = 1

F(n) = F(n-1) + F(n-2) для n > 1

Наивная рекурсивная реализация будет пересчитывать одни и те же подзадачи несколько раз, что приведет к экспоненциальной временной сложности. Используя динамическое программирование с нисходящим подходом (мемоизация), мы можем хранить результаты подзадач в кеше (словаре или хеш-таблице) и повторно использовать их, чтобы избежать избыточных вычислений. Вот простой для понимания пример на Ruby и Javascript:

Вот пример Руби:

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

Вот тот же код в 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

В этом примере мы определяем функцию fib, которая принимает желаемый индекс n и необязательный словарь memo для хранения вычисленных чисел Фибоначчи. Когда функция вызывается в первый раз, мемо пуст. Затем функция проверяет, есть ли результат для текущего ввода n уже в памятке. Если это не так, функция рекурсивно вычисляет результат и сохраняет его в памятке перед возвратом.

Таким образом, когда функция снова вызывается с тем же вводом n, она напрямую возвращает результат из мемо без его пересчета. Такой подход значительно снижает временную сложность алгоритма, делая его более эффективным.

Нахождение минимального количества монет, необходимого для внесения сдачи на заданную сумму

Рассмотрим задачу нахождения минимального количества монет, необходимого для внесения сдачи на заданную сумму. Нам дан массив номиналов монет и сумма. Цель состоит в том, чтобы найти наименьшее количество монет, которые составляют целевую сумму. Используя подход динамического программирования сверху вниз с мемоизацией, мы можем повысить эффективность нашего решения.

Вот пример динамического программирования сверху вниз (мемоизация) для минимального количества монет, необходимого для внесения сдачи на заданную сумму в ES6 (JavaScript) и 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)

В 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)

В этом примере мы определяем функцию min_coins, которая принимает целевое amount, доступное coins и необязательный словарь memo для хранения минимального количества монет, необходимого для каждой суммы. Когда функция вызывается в первый раз, мемо пуст. Затем функция проверяет, есть ли уже результат для текущей суммы в служебной записке. Если это не так, функция рекурсивно вычисляет результат и сохраняет его в памятке перед возвратом.

Используя мемоизацию, мы избегаем многократного пересчета минимального количества монет, необходимого для одной и той же суммы, что делает алгоритм более эффективным.