Динамічне програмування - проблеми, пов’язані з Grids HackerEarth
Ми бажаємо про конфіденційність ваших даних. HackerEarth використовує надану Вами інформацію для надання Вам актуального вмісту, продуктів та послуг.
Наша політика конфіденційності та використання послуг, що допомогли вам зрозуміти, як ви контролюєте свої дані на HackerEarth.
Зареєструйтесь та отримайте безкоштовний доступ до 100+ підручників та практичних завдань Начать
1. Вступ
У конкурсах кодування в Інтернеті є багато проблем, які передбачають пошук шляху із мінімальною вартістю в сітці, пошук кількості способів досягти певної позиції з певної вихідної точки у двовимірній сітці тощо. Цей пост намагається розглянути підхід динамічного програмування для вирішення цих проблем. Тут будуть розглянуті такі проблеми:
2. Пошук шляху мінімальних витрат у 2-D матриці
Постановка проблеми: Враховуючи матрицю витрат Cost [] [], де Cost [i] [j] позначає вартість відвідування комірки з координатами (i, j), знайдіть шлях мінімальної вартості, щоб дістатися до комірки (x, y) з комірки ( 0,0) за умови, що ви можете пройти лише один крок праворуч або один крок вниз. (Ми вважаємо, що всі витрати є натуральними числами)
Рішення: Дуже легко зауважити, що якщо ви досягли положення (i, j) у сітці, ви, мабуть, прибули з однієї клітинки вище, тобто (i-1, j), або з однієї комірки ліворуч, тобто (i, j-1). Це означає, що вартість відвідування комірки (i, j) буде походити від наступного відношення рецидиву:
Наведене вище твердження означає, що для досягнення комірки (i, j) з мінімальною вартістю спочатку досягайте комірки (i-1, j) або комірки (i, j-1) з якомога мінімальними витратами. Звідти перейдіть до комірки (i, j). Це підводить нас до двох важливих умов, які необхідно виконати для динамічної проблеми програмування:
Оптимальна підструктура: - Оптимальне вирішення проблеми передбачає оптимальне вирішення підзадачі.
Підпроблеми, що перекриваються: - Підпроблеми після обчислення можна зберігати в таблиці для подальшого використання. Це економить час, необхідний для обчислення тих самих підзадач знову і знову.
(Ви можете погуглити вищезазначені два терміни, щоб отримати докладнішу інформацію)
Проблема пошуку шляху мінімальних витрат зараз майже вирішена. Тепер ми обчислюємо значення базових випадків: верхній рядок і крайній лівий стовпець. Для верхнього рядка до комірки можна дістатися лише з комірки ліворуч від неї. Припускаючи нульовий індекс,
тобто вартість досягнення осередку (0, j) = Вартість досягнення осередку (0, j-1) + Вартість відвідування осередку (0, j) Аналогічним чином,
тобто вартість досягнення осередку (i, 0) = Вартість досягнення осередку (i-1,0) + Вартість відвідування осередку (i, 0)
З них можна обчислити інші значення. Дивіться код нижче для більш детального розуміння.
Інший варіант цієї проблеми включає інший напрямок руху, тобто також дозволяється переміщатися по діагоналі нижче від комірки (i, j) до комірки (i + 1, j + 1). Це питання також можна легко вирішити за допомогою невеликої модифікації відношення рецидивів. Щоб досягти (i, j), спочатку потрібно досягти або (i-1, j), (i, j-1) або (i-1, j-1).