Hints
Let us solve the 1D version of this problem:
You are given an array of n elements. Choose 2 indices i and j such that the cost
A[i] + A[j] + C*|i - j|
is minimized.
Can you come up with an algorithm to find the answer in O(n)?
dp[i] to be the minimum cost when the last station is built at node i. The answer to the original problem would then be max(dp[i]). Can you populate this DP in O(n)?
Notice that since this is the last station built, we can freely open |.|.
Therefore,
dp[i] = min(A[i] + A[j] + C*(i - j))
Now, let’s separate out the i and j parts.
dp[i] = min(A[i] + C*i + A[j] - C*j)
Can you now notice a way to popualte this DP in O(n)?
dp[i] = min(A[i] + C*i + A[j] - C*j)
Define contrib[i] = A[i] - C*i, Then, it’s easy to see that
dp[i] = min(A[i] + C*i + contrib[j])
dp[i] = A[i] + C*i + min(contrib[j])
Hence, dp[i] only depends on minimum contribution of previous elements. And the contribution doesn’t change, so these contributions can be computed in advance. Then, you can iterate from left to right, keeping track of minimum contribution seen so far and updating DP values.
Once you’ve populated DP values, the answer is min(dp[i]). Hence, we solved it for 1D.
Now, what is stopping you from applying this trick to the 2D version?
- There’s no concept of left and right in 2D matrix. Hence, you can’t open
|.|like in the 1D version. - Even if you were to open
|.|, for reach(i, j), as there is no concept of last node, so the the other cell could be anywhere.