Динамическое программирование (продолжение) — Основы алгоритмов и структур данных

В прошлых случаях состояние динамики описывалось одним параметром. Но не всегда все так просто: количество параметров, описывающих состояние, может быть намного больше. Попробуем решить задачу, где состояние динамики будет описываться двумя числами. Это и будет двумерной динамикой.

Есть тетрадный лист в клетку, 5 на 5 клеток, в каждой клетке есть какое-то количество долларов, мы стоим в левом верхнем углу (i = 0, j = 0).

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

Само игровое поле представим как массив массивов (матрицу). i - строки, j - столбцы.

const matrix = [
  [0, 0, 2, 0, 2],
  [1, 3, 2, 0, 1],
  [1, 0, 2, 8, 2],
  [3, 1, 1, 0, 0],
  [1, 0, 2, 4, 3],
];

matrix[1][1]; // 3

Посмотрим на пункты, которые нам необходимо знать:

• Состояние динамики. Состояние динамики определяется координатой на нашем листе, то есть параметрами, которые задают координату - i, j.
• Значения начальных состояний. За начальное состояние возьмем i-0, j-0, а также количество денег в matrix[0][0] // 0.
• Переходы между состояниями, формула пересчета. В этой задаче мы выбираем максимум, поскольку нам нужно найти как можно больше денег, поэтому переход из состояния в состояние будет выбором максимальной суммы денег на предыдущих клетках. Иными словами, если мы хотим попасть в matrix[1][1], мы должны выбрать, из какой клетки выгоднее прийти: из matrix[1][0] или matrix[0][1]. При этом нам необходимо предварительно выяснить, с какой суммой денег мы пришли в matrix[1][0] и в matrix[0][1]. То есть верхние и левые значения уже должны быть подсчитаны.
• Порядок пересчета. Тут как захотим, сейчас попробуем динамикой вперед.
• Расположение ответа на задачу. Это приход к matrix[4][4] с подсчитанным максимально полным кошельком.

const matrix = [
  [0, 0, 2, 0, 2],
  [1, 3, 2, 0, 1],
  [1, 0, 2, 8, 2],
  [3, 1, 1, 0, 0],
  [1, 0, 2, 4, 3],
];

for (i = 0; i <= 4; i += 1) {
  for (j = 0; j <= 4; j += 1) {
     if (j > 0 && i < 1) {
      matrix[i][j] += matrix[i][j - 1];
    }
    if (i > 0 && j < 1) {
      matrix[i][j] += matrix[i - 1][j];
    }
    if (i > 0 && j > 0) {
      matrix[i][j] += Math.max(matrix[i][j - 1], matrix[i - 1][j]);
    }
  }
}

/*
Матрица будет такой
[
  [0, 0, 2, 2, 4],
  [1, 4, 6, 6, 7],
  [2, 4, 8, 16, 18],
  [5, 6, 9, 16, 18],
  [6, 6, 11, 20, 23],
];
*/

matrix[4][4]; // 23;

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

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.