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

Представьте, что вам нужно выйти из дома (точка A) на работу (точка B), используя карту улиц вашего города. Это может быть очень утомительно и утомительно, учитывая различные комбинации улиц, которые могут быть между этими двумя местами. Теперь также учтите, что вы, вероятно, собираетесь делать эту операцию каждый день, потому что вам нужно приходить в офис каждое утро, и у каждого есть свой способ сделать это. Итак, вы один раз ищете лучший способ добраться туда, а затем вспоминаете его, представляете, насколько утомительно может быть каждый день искать один и тот же путь! Это то, что позволяет нам достичь динамическое программирование.

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

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

Вот простой пример в псевдокоде:

// We have a larger scope for the solutions than for the function itself. In Javascript this can be used as closures.
solutions = array()
function add(x, y) {
   if solutions[x][y] exists then
      return solutions[x][y]
   solutions[x][y] = solutions[y][x] = x + y // Sum is commutative
   return solutions[x][y]
}
add(2, 3) 
// Executes the operation because there's no result for that parameter combination
add(2, 3) 
// Now it just simply uses direct access to return the solution calculated on the previous call.

Конечно, за небольшую сумму это чрезмерная инженерия. Но подумайте о последовательности Фибоначчи, она бесконечна и использует предыдущую последовательность Фибоначчи с предыдущими числами, чтобы получить то, что искали.

Вот псевдокод приложения динамического программирования к последовательности Фибоначчи.

table = array()
fibonacci(n) {
   if table[n] exists 
      return table[n]
   if n = 0 then 
      return 0
   if n = 1 then
      return 1
   table[n] = fibonacci(n - 1) + fibonacci(n - 2)
   return table[n]  
}

В этом примере вы можете вычислить фибоначчи (6), которое равно 8. Но вычисляя это, вы также сохраняете последовательность Фибоначчи для всех предыдущих чисел. Поэтому, если мне нужно вычислить фибоначчи (5), он уже был рассчитан, поэтому я получаю результат быстрее, чем если бы мне пришлось вычислять его заново.