Восстановление ответа: через массив динамики и через массив предков.

Материал из Algocode wiki
Перейти к: навигация, поиск

Восстановление ответа

Теперь мы умеем находить ответ в задачах на ДП, но в некоторых задачах нам также интересно как мы можем его получить, например в задаче про черепашку нам может быть интересен путь. Такую задачу называют восстановлением ответа в динамике.

Есть два способа, которыми можно это сделать.

1) Хранить в массив prev откуда ты пришел в эту клетку.

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

 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             if (dp[i - 1][j] > dp[i][j - 1]) {
18                 prev[i][j] = 1;
19             }
20             else {
21                 prev[i][j] = 0;
22             }
23         }
24     }
25 }

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

 1 while (i > 0 or j > 0) {
 2     if (prev[i][j] == 1) {
 3         i -= 1;
 4         answer_directions.push_back("DOWN");
 5     }
 6     else {
 7         j -= 1;
 8         answer_directions.push_back("RIGHT");
 9     }
10     answer.push_back({i, j});
11 }
12 reverse(answer.begin(), answer.end());
13 reverse(answer_directions.begin(), answer_directions.end());

2) Вместо хранения массива prev догадаться по массиву dp, откуда именно черепашка пришла в эту клетку.

В данном примере это довольно легко. Если мы уже посчитали весь массив dp, то теперь можно начиная с конца легко понять, пришла черепашка туда сверху или слева в оптимальном маршруте - она пришла из клетки с максимальным числом монет.

 1 while (i > 0 or j > 0) {
 2     if (i != 0 && (j == 0 || dp[i - 1][j] > dp[i][j - 1]))
 3         i -= 1;
 4         answer_directions.push_back("DOWN");
 5     else {
 6         j -= 1;
 7         answer_directions.psuh_back("RIGHT");
 8     }
 9     answer.append({i, j})
10 }
11 reverse(answer.begin(), answer.end());
12 reverse(answer_directions.begin(), answer_directions.end());