Восстановление ответа: через массив динамики и через массив предков.: различия между версиями
Глеб (обсуждение | вклад) |
Глеб (обсуждение | вклад) |
||
Строка 43: | Строка 43: | ||
if (prev[i][j] == 1) { | if (prev[i][j] == 1) { | ||
i -= 1; | i -= 1; | ||
− | answer_directions.push_back( | + | answer_directions.push_back("DOWN"); |
} | } | ||
else { | else { | ||
j -= 1; | j -= 1; | ||
− | answer_directions.push_back( | + | answer_directions.push_back("RIGHT"); |
} | } | ||
− | answer.push_back( | + | answer.push_back({i, j}); |
} | } | ||
reverse(answer.begin(), answer.end()); | reverse(answer.begin(), answer.end()); | ||
Строка 63: | Строка 63: | ||
if (i != 0 && (j == 0 || dp[i - 1][j] > dp[i][j - 1])) | if (i != 0 && (j == 0 || dp[i - 1][j] > dp[i][j - 1])) | ||
i -= 1; | i -= 1; | ||
− | answer_directions. | + | answer_directions.push_back("DOWN"); |
else { | else { | ||
j -= 1; | j -= 1; | ||
− | answer_directions. | + | answer_directions.psuh_back("RIGHT"); |
} | } | ||
− | answer.append( | + | answer.append({i, j}) |
} | } | ||
reverse(answer.begin(), answer.end()); | reverse(answer.begin(), answer.end()); | ||
reverse(answer_directions.begin(), answer_directions.end()); | reverse(answer_directions.begin(), answer_directions.end()); | ||
</syntaxhighlight> | </syntaxhighlight> |
Версия 13:56, 5 октября 2019
Восстановление ответа
Теперь мы умеем находить ответ в задачах на ДП, но в некоторых задачах нам также интересно как мы можем его получить, например в задаче про черепашку нам может быть интересен путь. Такую задачу называют восстановлением ответа в динамике.
Есть два способа, которыми можно это сделать.
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());