CODEWITHSUNDEEP
algorithmdynamic-programming
Mike Chan
Mike Chan

Reputation: 337

Trying to optimize DP solutions from 2D Array to 1D Array

I've been trying to wrap my head around the fact that a lot of DP questions that involve bottom up tabulation via a 2D Matrix can be simplified into a 1D Array to save on space since you only rely on the previous two rows but I don't really understand the why/how/intuition behind this.

Just wondering if anyone could offer the most dumb downed version of why this works...

Upvotes: 1

Views: 973

Answers (1)

wLui155
wLui155

Reputation: 742

Generally, we use can apply DP when the optimal solution to a given problem can be determined from the optimal solutions of its subproblems. When coming up with a solution to some algorithm, it usually helps to come up with a recursive one first. From there, if we observe that recursive subproblems are re-calculated multiple times, we can just memoize the intermediate results for fast reference to them later.

In some special cases, we don't actually need to remember the solution to all subproblems at once; we just need to know a certain subset at a time.

The space optimization described above seems to best answer to the question you're asking - how does one condense the total set of solutions as a 2D matrix into a single 1D array? Well, at a given time, we don't actually store all solutions (the 2D matrix) in any single point in time; we just store what is needed to calculate the next round of intermediate/final outputs in the algorithm.

Perhaps walking through an example application may help reinforce this description. A nice example is the generalized stock trading problem. Basically, we have an input array prices of a stock on a given day and would like to calculate the maximum profit that can be earned if k buy-sell transactions are made, where one stock may be bought and held at any given time.

The trickiest part in my opinion is figuring out how to move from the one transaction case to the two transaction case. I'll assume we're proficient enough in dynamic programming to move immediately to the k transaction case. Notice that a nice formulation of the problem in terms of subproblems is the following:

prices = input array of prices, length is n
Define dp[k][i] = maximum profit earned by day i, after having made k transactions
dp[k][i] = max(dp[k][i - 1], (prices[i] + effectivePrice)
effectivePrice = max(dp[k - 1][i] - prices[i], effectivePrice) (compute on the fly for each i)

Now in this particular case our "naive" dp solution has a 2D matrix with k rows and n columns. The space reduction here is that, in order to calculate the result for k transactions, we only need knowledge of the case for k - 1 transactions. Therefore, it is certainly possible to solve the problem using two 1D arrays of size n.

Let oldDp = solution for the k - 1 case
Let newDp = solution for the k case (computed on the fly)
for each transaction:
    for each day i:
        newDp[i] = max(newDp[i - 1], (prices[i] + effectivePrice)
        effectivePrice = max(oldDp[i] - prices[i], effectivePrice)

    // Set up for next iteration
    oldDp = newDp
    newDp = blank array of size n

As we can see, we managed to save a lot of space - we went from having to use a 2D matrix with k rows and n columns to two 1D arrays of size n. An even better optimization is to just use a single 1D array; this is possible since the only indices that we examine in oldDp is the current one i when calculating effectivePrice. Because we only need to temporarily remember the old result for day i, we can just make use of a temporary variable. Thus, the optimized pseudocode (for our "naive" approach) appears as below:

Let dp = maximum profit, so that dp[i] = maximum profit after k transactions (built iteratively) on day i.
for each transaction:
    for each day i:
        // At this point, dp[i] is equivalent to dp[k - 1][i], yet
        // for all j < i, dp[j] is equivalent to dp[k][j]!
        temp = dp[i]
        dp[i] = max(dp[i - 1], prices[i] + effectivePrice)
        effectivePrice = max(temp - prices[i], effectivePrice)

And so, using the "naive" idea of determining the optimal solution after k transactions from k - 1 transactions, we optimize space by going from a 2D matrix of size kn to a 1D array of size n.

Upvotes: 2

Related Questions