Восстановление ответа: через массив динамики и через массив предков.: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «Восстановление ответа Теперь мы умеем находить ответ в задачах на ДП, но в некоторых зад...») |
Глеб (обсуждение | вклад) |
||
Строка 8: | Строка 8: | ||
Когда мы выбираем максимум из левой и верхней клетки, мы на самом деле решаем, какой последний ход будет в оптимальном пути до этой клетки - сверху или слева, и берем ответ для той клетки, сложнный с монетами в этой клетке. Давайте координаты клетки, откуда мы пришли, хранить в массиве prev. Или, в данном случае, можно хранить не координаты а просто 1, если пришли слева, и 0, если пришли сверху. | Когда мы выбираем максимум из левой и верхней клетки, мы на самом деле решаем, какой последний ход будет в оптимальном пути до этой клетки - сверху или слева, и берем ответ для той клетки, сложнный с монетами в этой клетке. Давайте координаты клетки, откуда мы пришли, хранить в массиве prev. Или, в данном случае, можно хранить не координаты а просто 1, если пришли слева, и 0, если пришли сверху. | ||
+ | |||
+ | <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]; | ||
+ | if (dp[i - 1][j] > dp[i][j - 1]) { | ||
+ | prev[i][j] = 1; | ||
+ | } | ||
+ | else { | ||
+ | prev[i][j] = 0; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | И, чтобы восстановить ответ, надо просто пройтись с конца по этим клеткам до самого начала, и развернуть получившуюся последовательность. | ||
+ | |||
+ | <syntaxhighlight lang="C++" line='line'> | ||
+ | while (i > 0 or j > 0) { | ||
+ | if (prev[i][j] == 1) { | ||
+ | i -= 1; | ||
+ | answer_directions.push_back('DOWN'); | ||
+ | } | ||
+ | else { | ||
+ | j -= 1; | ||
+ | answer_directions.push_back('RIGHT'); | ||
+ | } | ||
+ | answer.push_back((i, j)); | ||
+ | } | ||
+ | reverse(answer.begin(), answer.end()); | ||
+ | reverse(answer_directions.begin(), answer_directions.end()); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | 2) Вместо хранения массива prev догадаться по массиву dp, откуда именно черепашка пришла в эту клетку. | ||
+ | |||
+ | В данном примере это довольно легко. Если мы уже посчитали весь массив dp, то теперь можно начиная с конца легко понять, пришла черепашка туда сверху или слева в оптимальном маршруте - она пришла из клетки с максимальным числом монет. | ||
+ | |||
+ | <syntaxhighlight lang="C++" line='line'> | ||
+ | while (i > 0 or j > 0) { | ||
+ | if (i != 0 && (j == 0 || dp[i - 1][j] > dp[i][j - 1])) | ||
+ | i -= 1; | ||
+ | answer_directions.append('DOWN'); | ||
+ | else { | ||
+ | j -= 1; | ||
+ | answer_directions.append('RIGHT'); | ||
+ | } | ||
+ | answer.append((i, j)) | ||
+ | } | ||
+ | reverse(answer.begin(), answer.end()); | ||
+ | reverse(answer_directions.begin(), answer_directions.end()); | ||
+ | </syntaxhighlight> |
Версия 08:32, 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 }
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 if (dp[i - 1][j] > dp[i][j - 1]) {
15 prev[i][j] = 1;
16 }
17 else {
18 prev[i][j] = 0;
19 }
20 }
21 }
22 }
И, чтобы восстановить ответ, надо просто пройтись с конца по этим клеткам до самого начала, и развернуть получившуюся последовательность.
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.append('DOWN');
5 else {
6 j -= 1;
7 answer_directions.append('RIGHT');
8 }
9 answer.append((i, j))
10 }
11 reverse(answer.begin(), answer.end());
12 reverse(answer_directions.begin(), answer_directions.end());