I wrote an article about Hirschberg's Algorithm
This article was originally written in Japanese here http://www.learning-algorithms.com/entry/2018/01/22/024722
Firstly, look at the problem below.
https://csacademy.com/contest/archive/task/classic-task/
Summary: You are given a H×W grid which has a number in each cell. You want to go to the lower right cell from the upper left cell, and the score is the sum of the nunbers of the cells you pass through. Minimize the score, and show an example of the paths which satisfy the score. H ≤ 10000, W ≤ 10000.
If you just need to calculate the minimum score, you can solve this problem by a simple DP with the time complexity O(HW).
dp(x, y) = grid(x, y) + min(dp(x - 1, y), dp(x, y - 1))
Let me show the grids on which the numbers and the DP values are written.
In this example, you found out that the minimum score is 29. Now, let's restore the path which gets the score. On DP grid that I showed above, you can restore DP from the last cell. When you are on a cell in the optimal path, the previous cell must be the cell which has the smaller DP value. For each cell, therefore, just write 1, if the nuber in the upper cell is smaller than that in the left cell, and 0, vice versa. In this way, you can get the grid like the left of the image, and the optimal path can be restored.
What I wrote above is simply implemented. It's a piece of cake!
vector<vector<long long>> dp(h, vector<long long> (w, INFL));
dp[0][0] = grid[0][0];
for (int i = 0; i < h; i ++) {
for (int j = 0; j < w; j ++) {
if (i - 1 >= 0) dp[i][j] = min(dp[i][j], (long long) grid[i][j] + dp[i - 1][j]);
if (j - 1 >= 0) dp[i][j] = min(dp[i][j], (long long) grid[i][j] + dp[i][j - 1]);
}
}
vector<bitset<10010>> restore(10010);
for (int i = 0; i < h; i ++) {
for (int j = 0; j < w; j ++) {
if (i == 0) {
restore[i][j] = false;
} else if (j == 0) {
restore[i][j] = true;
} else {
restore[i][j] = dp[i - 1][j] < dp[i][j - 1];
}
}
}
int y = h - 1, x = w - 1;
string ans = "";
while (true) {
if (x == 0 && y == 0) break;
if (restore[y][x]) {
ans += "D";
y --;
} else {
ans += "R";
x --;
}
}
reverse(ans.begin(), ans.end());
cout << ans << endl;
This problem seemed quite easy for many coders, but if you look at the problem statement again, you'll notice that the memory limit is unusual (it's emphasized though!). This memory limit implies that you can't even use memory space O(HW).
If you just want to know the minimum score, you can do the same DP by reusing the 2 DP arrays, but how do you restore the path?
One possible solution is to restore the path from right side by reusing the 2 restoring arrays. However, since you can't save the DP values, every time you restore one step of the path, you need to do the DP from the left side again, which unfortunately requires the time O(HW * min(H, W)). Not fast enough!
This problem can be solved by Hirschberg's Algorithm! This algorithm makes it possible to restore this DP within space O(min(H, W)), and time O(HW), respectively.
This algorithm is based on Divide and Conquer Algorithm. Dividing the grids, Finding the path on each grid, and merging them.
Let's see this algorithm, using the same example above. First of all, divide the grid into two (almost) same size grids. According to the rule of the movement, there must be only one position, where you pass from the left grid to the right grid.
In order to find the position, you just do the DP from the upper left to the lower right on the left grid, while you do the DP from the lower right to the upper left on the right grid.
Consequently, at each position on the line of the division, the score was calculated from the upper left and from the lower right, thus, the position where these sums are the minimum, must be used. In this example, these sums are 35, 33, 29, 36 from the top, which implies that the 3rd position from the top should be used.
Then, just repeat this process until all the movement is restored. The second time, you need to consider only the following part.
This means that you need to traverse only half part than you previously traversed. In the third time, you only need to check the 
part of the entire grid.
The space complexity is obviously O(min(H, W)), while the time complexity is
I hope you enjoyed this algorithm!
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <string>
using namespace std;
template<class T>
void amin(T &a, T b) { if (a > b) a = b; }
int main() {
int h, w;
scanf("%d%d", &h, &w);
vector<int> u(h), v(w);
for (int i = 0; i < h; i ++) scanf("%d", &u[i]);
for (int i = 0; i < w; i ++) scanf("%d", &v[i]);
function<long long (int, int)> get_val = [&](int i, int j) {
return (long long) (u[i] + j + 1) ^ (long long) (v[j] + i + 1);
};
//Hirschberg
vector<pair<int, int>> pos;
function<void (int, int, int, int)> Hirschberg = [&](int li, int lj, int ri, int rj) {
int mid = (lj + rj) / 2;
int height = ri - li + 1;
if (rj - lj < 1) return;
if (height == 1) {
pos.emplace_back(mid, li);
Hirschberg(li, lj, li, mid);
Hirschberg(li, mid + 1, li, rj);
return;
}
//left
int w_left = mid - lj + 1;
vector<vector<long long>> dp(2, vector<long long> (height));
dp[0][0] = get_val(li, lj);
for (int i = 1; i < height; i ++) {
dp[0][i] = dp[0][i - 1] + get_val(li + i, lj);
}
bool f = 1;
for (int j = 1; j < w_left; j ++) {
for (int i = 0; i < height; i ++) {
dp[f][i] = 1LL << 60;
}
for (int i = 0; i < height; i ++) {
int val = get_val(li + i, lj + j);
amin(dp[f][i], dp[!f][i] + val);
if (i - 1 >= 0) amin(dp[f][i], dp[f][i - 1] + val);
}
f = !f;
}
f = !f;
vector<long long> m1(height);
for (int i = 0; i < height; i ++) {
m1[i] = dp[f][i];
}
//right
int w_right = rj - mid;
dp[0][0] = get_val(ri, rj);
for (int i = 1; i < height; i ++) {
dp[0][i] = dp[0][i - 1] + get_val(ri - i, rj);
}
f = 1;
for (int j = 1; j < w_right; j ++) {
for (int i = 0; i < height; i ++) {
dp[f][i] = 1LL << 60;
}
for (int i = 0; i < height; i ++) {
long long val = get_val(ri - i, rj - j);
amin(dp[f][i], dp[!f][i] + val);
if (i - 1 >= 0) amin(dp[f][i], dp[f][i - 1] + val);
}
f = !f;
}
f = !f;
vector<long long> m2(height);
for (int i = 0; i < height; i ++) {
m2[height - i - 1] = dp[f][i];
}
//
long long mi = 1LL << 60;
int res = -1;
for (int i = 0; i < height; i ++) {
long long sum = m1[i] + m2[i];
if (sum < mi) {
mi = sum;
res = i;
}
}
res += li;
pos.emplace_back(mid, res);
Hirschberg(li, lj, res, mid);
Hirschberg(res, mid + 1, ri, rj);
};
Hirschberg(0, 0, h - 1, w - 1);
//
sort(pos.begin(), pos.end());
int y = 0, x = 0;
string ans = "";
while (true) {
if (x == w - 1) {
while (y != h - 1) {
ans += "D";
y ++;
}
break;
}
if (pos[x].second == y) {
x ++;
ans += "R";
} else {
y ++;
ans += "D";
}
}
cout << ans << endl;
return 0;
}
Комментарии (0)
