Двумерное ДП: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «Двумерная динамика: черепашка Теперь рассмотрим такую задачу: На каждой клетке двумерн...») |
Глеб (обсуждение | вклад) |
||
(не показано 5 промежуточных версий этого же участника) | |||
Строка 14: | Строка 14: | ||
] | ] | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | Тут нас снова спасает динамика. Давайте сводить задачу к предыдущей! Задачей назовем "сколько максимально монет можно набрать на пути от $0\times0$ до $i\times j$" (заменим 1-нумерацию на 0-нумерацию). Будем хранить это в двумерном массиве $dp$ в клетке $dp[i][j]$. | ||
+ | |||
+ | Сразу понятны некоторые свойства этого массива: | ||
+ | * Он размера $n \times m$ | ||
+ | * $dp[0][0] = COINS[0][0]$ | ||
+ | * ответ на всю задачу лежит в $dp[n - 1][m - 1]$ | ||
+ | |||
+ | Но гораздо важнее придумать формулу для подсчета $dp[i][j]$ через предыдущие. Легко посчитать первую строку и первый столбец: | ||
+ | * $dp[0][k] = dp[0][k - 1] + COINS[0][k]$ | ||
+ | * $dp[k][0] = dp[k - 1][0] + COINS[k][0]$ | ||
+ | |||
+ | Так как до этих клеток есть ровно один путь. | ||
+ | |||
+ | Но что делать, если есть много путей до клетки $dp[i][j]$? Снова разобьем их на на несколько групп в зависимости от последнего хода (! важный трюк, запомните). Последний ход был: | ||
+ | * либо из $[i][j - 1]$ | ||
+ | * либо из $[i - 1][j]$ | ||
+ | |||
+ | Поэтому формула для максимального числа монет такая: $dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + COINS[i][j]$. | ||
+ | |||
+ | Ну все, достаточно пройтись правильно по двумерному массиву (построчно сверху вних, а в каждой строке слева направо) и заполнить этот массив. | ||
+ | |||
+ | <syntaxhighlight lang="C++" line='line'> | ||
+ | for (int i = 0; i < n; i++) { | ||
+ | for (int j = 0; j < m; j++) { | ||
+ | if (i == 0 && j == 0) { | ||
+ | dp[0][0] = COINS[0][0]; | ||
+ | prev[0][0] = -1 # это самое начало, предыдущей клетки нет | ||
+ | } | ||
+ | else if (i == 0) { | ||
+ | dp[0][j] = dp[0][j - 1] + COINS[0][j]; | ||
+ | prev[0][j] = 0 # слева пришли | ||
+ | } | ||
+ | else if (j == 0) { | ||
+ | dp[i][0] = dp[i - 1][0] + COINS[i][0]; | ||
+ | prev[i][0] = 1 # сверху пришли | ||
+ | } | ||
+ | else { | ||
+ | dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + COINS[i][j]; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 16:29, 10 октября 2019
Двумерная динамика: черепашка Теперь рассмотрим такую задачу:
На каждой клетке двумерной таблички написано, сколько там лежит монет. Черепашка стоит в клетке $1 \times 1$ (верхней левой), и может двигаться только на одну клетку вниз, или на одну клетку вправо. Нужно найти максимальное число монет, которое может набрать черепашка по пути к нижней правой клетке $N \times M$.
Первое, что приходит в голову - это просто идти черепашкой в ту клетку из соседних, где лежит больше монет. К сожалению, эта жадная стратегия не всегда работает. Например, на такой доске жадная черепашка пошла бы по следу из единичек, хотя гораздо выгоднее пойти сначала по нулям, а потом найти там большие горстки монет (40, 70, 100):
1 COINS = [
2 [0, 1, 1, 1, 1, 1],
3 [0, 0, 0, 0, 0, 1],
4 [0, 40, 70, 0, 0, 1],
5 [100, 0, 0, 0, 0, 1]
6 ]
Тут нас снова спасает динамика. Давайте сводить задачу к предыдущей! Задачей назовем "сколько максимально монет можно набрать на пути от $0\times0$ до $i\times j$" (заменим 1-нумерацию на 0-нумерацию). Будем хранить это в двумерном массиве $dp$ в клетке $dp[i][j]$.
Сразу понятны некоторые свойства этого массива:
- Он размера $n \times m$
- $dp[0][0] = COINS[0][0]$
- ответ на всю задачу лежит в $dp[n - 1][m - 1]$
Но гораздо важнее придумать формулу для подсчета $dp[i][j]$ через предыдущие. Легко посчитать первую строку и первый столбец:
- $dp[0][k] = dp[0][k - 1] + COINS[0][k]$
- $dp[k][0] = dp[k - 1][0] + COINS[k][0]$
Так как до этих клеток есть ровно один путь.
Но что делать, если есть много путей до клетки $dp[i][j]$? Снова разобьем их на на несколько групп в зависимости от последнего хода (! важный трюк, запомните). Последний ход был:
- либо из $[i][j - 1]$
- либо из $[i - 1][j]$
Поэтому формула для максимального числа монет такая: $dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + COINS[i][j]$.
Ну все, достаточно пройтись правильно по двумерному массиву (построчно сверху вних, а в каждой строке слева направо) и заполнить этот массив.
1 for (int i = 0; i < n; i++) {
2 for (int j = 0; j < m; j++) {
3 if (i == 0 && j == 0) {
4 dp[0][0] = COINS[0][0];
5 prev[0][0] = -1 # это самое начало, предыдущей клетки нет
6 }
7 else if (i == 0) {
8 dp[0][j] = dp[0][j - 1] + COINS[0][j];
9 prev[0][j] = 0 # слева пришли
10 }
11 else if (j == 0) {
12 dp[i][0] = dp[i - 1][0] + COINS[i][0];
13 prev[i][0] = 1 # сверху пришли
14 }
15 else {
16 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + COINS[i][j];
17 }
18 }
19 }
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin