Двумерное ДП: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «Двумерная динамика: черепашка Теперь рассмотрим такую задачу: На каждой клетке двумерн...»)
 
Строка 13: Строка 13:
 
     [100, 0,  0,  0,  0,  1]
 
     [100, 0,  0,  0,  0,  1]
 
]
 
]
 +
</syntaxhighlight>
 +
Тут нас снова спасает динамика. Давайте сводить задачу к предыдущей! Задачей назовем "сколько максимально монет можно набрать на пути от $0\times0$ до $i\times j$" (заменим 1-нумерацию на 0-нумерацию). Будем хранить это в двумерном массиве dp в клетке dp[i][j].
 +
 +
Сразу понятны некоторые свойства этого массива:
 +
* Он размера NxM
 +
* 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];
 +
        }
 +
        else if (i == 0) {
 +
            dp[0][j] = dp[0][j - 1] + COINS[0][j];
 +
        }
 +
        else if (j == 0) {
 +
            dp[i][0] = dp[i - 1][0] + COINS[i][0];
 +
        }
 +
        else {
 +
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + COINS[i][j];
 +
        }
 +
    }
 +
}
 
</syntaxhighlight>
 
</syntaxhighlight>

Версия 08:12, 5 октября 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].

Сразу понятны некоторые свойства этого массива:

  • Он размера NxM
  • 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         }
 6         else if (i == 0) {
 7             dp[0][j] = dp[0][j - 1] + COINS[0][j];
 8         }
 9         else if (j == 0) {
10             dp[i][0] = dp[i - 1][0] + COINS[i][0];
11         }
12         else {
13             dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + COINS[i][j];
14         }
15     }
16 }