Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

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

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

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

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

1

Само игровое поле представим как массив массивов (матрицу). 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;

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


Аватары экспертов Хекслета

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

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

Ошибки, сложный материал, вопросы >
Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

  • задайте вопрос. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
  • расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
  • изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
900
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 130 курсов, 2000+ часов теории
  • 900 практических заданий в браузере
  • 360 000 студентов
Даю согласие на обработку персональных данных, соглашаюсь с «Политикой конфиденциальности» и «Условиями оказания услуг»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Даю согласие на обработку персональных данных, соглашаюсь с «Политикой конфиденциальности» и «Условиями оказания услуг»