An Approach for DP Problem

Start with the problem (src: leetcode#714)

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

How do we know it’s a Dynamic Programming (DP) problem? 💭

It’s based on your sense ;) But there are some signs that you can follow

• You don’t have a straight way to get the answer, let’s say the answer of problem set size i can only know if you know the answer for problem set size i'
• Each stage, while you try to find the answer through the input, there are multi possible choice that affects the later stages

If you can see one of those signs clearly, you’re better ready to face a DP problem.

Now how can we approach it? 💡

Let’s say dp[i] represents the max profit we can get if the sequence end at index i. We can then see that it doesn’t make sense to buy a stock at the last stage, so if i is the last stage, there is no reason to buy at i. Which mean the answer at i would be:

• Do nothing at i (no buy no sell).
• Sell at i (thus we have to buy previously).

Which mean

dp[i] = max(dp[i], dp[j-1] + prices[i] - prices[j] - fee)

The reason why it has to be dp[j-1] instead of dp[j] is what we say previously, we have to buy previously before we can sell. So if it’s dp[j], the formula will be dp[j] - prices[j] which leads to the wrong answer if dp[j] is the max profit if we sell at j (it’s mean to we can’t buy j right the time we sell j).

The formula represents for: the answer of sequence end at i will be calculated based on trying to sell at i with stock buy at j.

And that’s right, because dp[j-1] is the max possible profit we got right before we can buy a stock at j.

Anything missed?

We said that the answer at i (aka. dp[i]) must be one of either sell or do nothing at i, so for the case of do nothing at i

dp[i] = dp[i-1]

That would be the base value we set to dp[i] before we find max with sell previously bought stock.

Then we have the code

class Solution {
public:
    int maxProfitSlow(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<int> dp(n, 0);
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i-1];
            for (int j = 0; j < i; j++) {
                int prev = j ? dp[j-1] : 0;
                dp[i] = max(dp[i], prev + prices[i] - prices[j] - fee);
            }
        }
        return dp[n-1];
    }
}

The time complexity for this solution will be $O(n^{2})$ based on 2 nested for loops, and the space complexity will be $O(n)$.

Can we make it better? 🤔

One of the nice methods to optimize a DP formula is the math formula rearrangement. By combining j related operands, we have

dp[i] = max(dp[j-1] - prices[j] + prices[i] - fee)

The (prices[i] - fee) is constant for each iteration at i. That means we have to find max(dp[j-1] - prices[j]) to maximize dp[i].

Since it’s a simple max value and we only care about the only one greatest value before each i (i iterate 1..n so one way increasing) => We can use a variable to maintain that max 👌

class Solution {
public:
    int maxProfitOpt(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<int> dp(n, 0);
        int curMax = -prices[0]; // buy at 0

        for (int i = 0; i < n; i++) {
            if (i) dp[i] = dp[i - 1];

            dp[i] = max(dp[i], curMax + prices[i] - fee);
            // Maintain the max dp[j-1] - prices[j]
            curMax = max(curMax, (i ? dp[i - 1] : 0) - prices[i]);
        }

        return dp[n - 1];
    }
}

The time complexity for this solution will be $O(n)$, and the space complexity will be $O(n)$.

Anything else to optimize? 🧐

As a DP solution, your formula would be of kind:

F(x) = F(x-1) ~ and something

The formula says that to calculate F(x), you have to know F(x-1), which leads to 2 things you should be aware for a better implementation:

• You need to calculate (x-1) before (x), which mean your for loop would be i = 1..n (visit the small first then go to the bigger one)
• The F(x) only depends on F(x-1) (ie. this problem) or depends on other F(y)

The first point is being used to implement the previous 2 solutions; well done 🙌. What about the other?

Since our dp[i] only depends on dp[i-1], which means we don’t need the whole array dp(n), we just need the previous dp[i-1] while calculating dp[i]. One simple variable can do that.

class Solution {
public:
    int maxProfitBest(vector<int>& prices, int fee) {
        int n = prices.size();
        int ans = 0, prev = 0;
        int curMax = -prices[0]; // buy at 0

        for (int i = 0; i < n; i++) {
            ans = max(ans, curMax + prices[i] - fee);
            curMax = max(curMax, prev - prices[i]);
            prev = ans;
        }

        return ans;
    }
}

The time complexity for this solution will be $O(n)$, and the space complexity will be only $O(1)$. Probably the best possible solution 🚀

Take out

So there are a few things from the post I guess we better remember as tools in our pocket.

• Math formula rearrangement does it work to optimize the DP solution based on the DP formula.
• Based on the DP formula, we can find insight for implementation, how do we iterate through the input? should we store the whole previous stages? and so on.

That’s all, happy coding 🙌

• algorithm