Introduction
Recently, the cryptocurrency market is very interesting. We enjoy making profits from it. But, how can we maximize the profit?
As a developer, I believe there have some algorithms that can pull this job. And I find it in my notebook of a college course, which, of course, I’ve already forgotten how it works :).
It’s time to pick it up. The algorithm that seeks the optimal solution is Dynamic Programming.
Dynamic Programming
The best way to find the optimal solution is to backtrack the path of getting this solution.
Suppose that the best solution is f(n) , we need to know how to get to f(n) , which means to find out the equation.
f(n) = g[f(n-1)]If f(n) is the best solution of nth step, then g[f(n-1)] is the move from the best solution of (n-1)th step to nth step.
In brief, Dynamic Programming can chunk up an optimal problem into multiply optimal sub-problems.
You may ask, the normal backtracking algorithm can do that, too. What makes Dynamic Programming special? Dynamic Programming caches the sub-optimal solution.
The normal backtracking algorithm doesn’t cache the sub-optimal solution, it wastes a lot of time on recalculation. However, Dynamic Programming learns from history. When it meets f(i) , it will use f(i) in the cache.
To sum up, Dynamic Programming is an algorithm that seeks the optimal solution. The optimal solution must be got from optimal sub-solutions in the past, not the future. And it can memorize the optimal sub-solutions and use them in the current solution.
Enough theory, let’s maximize the profit!
Problem
You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k. Find the maximum profit you can achieve. You may complete, at most, k transactions. You must sell the stock before you buy again. (https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/)
The optimal solution is, on the last day, we have the max profit.
First, let’s see what influences the profit.
- Number of transaction: It’s limited by
k - State of buying or selling: when you buy or sell a share, the profit will change
- Price of day
With this information, we can initialize the cache.
profit = [{"sell": 0, "buy": -prices[0]} for _ in range(k + 1)]We can the states of transactions, from 0 transactions to k transactions. Each transaction has 2 profits, profit when selling a share or buying a share. profit of selling is initialized by 0. The profit of buying is initialized by -prices[0] .
We can make k transactions every day. Suppose that we are doing the ith transaction.
The max profit when we are going to sell a share is the max value of holding the share or selling it at the day price. The profit of selling it is the sum of the profit of buying a share of the current transaction and the day price.
profit[i]["sell"] = max(
profit[i]["sell"],
profit[i]["buy"] + prices[day])The max profit when we are going to buy a share is the max value of holding the share or buying it at the day price. The profit of buying it is the sum of the profit of selling a share of the previous transaction and the day price.
profit[i]["buy"] = max(
profit[i]["buy"],
profit[i - 1]["sell"] - prices[day],)The key point is to distinguish the current transaction and the previous transaction when we buy or sell a share.
Finally, the max profit is the max value of selling a share.
return max([trans["sell"] for trans in profit])Here is the full script.
Another way
Previously, we cache the profits by transactions. We can cache them by days, too.
profit = [[0 for _ in range(days)] for _ in range(3)]We initialize the profits of each day are 0. We need to add another dimension to track the transaction. There are 3 states of transaction: no transaction, previous transaction, and current transaction.
However, using this initialization, we lose the track of the profit of selling or buying a share. So, we set profit for the profits of selling. We use a variable to keep the max profit of buying for each transaction.
This method uses less space to cache the profits. However, it’s more difficult to write and understand. Because it not only uses an array but also a variable to cache the profits.
Both two transactions apply the notion of the current transaction and the previous one, which, again, it’s the key point of the solution.
Conclusion
Dynamic Programming can seek the optimal solution. Back to the topic, How can we make more money using it? We need to know the limit of the number of transactions, track the profit when we sell or buy a share, and have the price of the share every day.
Oh no. The last condition is a little bit difficult. It seems that we need a time machine to go to the future, get the prices, come back and make the decision.
OK, That’s fine. Now we just need to build a time machine.
