In this tutorial, I will go over a simple dynamic programming example. Dynamic programming simply refers to breaking down a complicated problem into simpler sub-problems and saving their results to refer back. I think of dynamic programming as an extension to recursion where we store its child recursive solutions, or more simply recursion + memoization.
Let's take a look at an example. Assume that you somehow have the ability to predict stock market for the next N days. Say you can trade stock exactly once a day, and the total number of trades you can make within the next N days is constrained to some number, say n. In addition, you can not own more than 1 stock at a time.
So, basically, given stock prices for next N consecutive days, [x1, x2, ..., xN], and given maximum of n total trades all on different days, when will you buy and sell each stock so that you can maximize the profit? Note that you must buy-sell-buy-sell and so forth with no consecutive buys or sells.
For example, if the next 5 day market price will be [5, 2, 2, 5, 3], and if I have at most 2 buy-sell trades to do, then I would buy on day 2 or 3 and sell on day 4, leaving me with +3 in profit. I will buy-sell only once, since this maximizes the profit.
It is easy when N is small, but it gets very difficult as N grows large. Given N = 50 with prices given by [8, 44, 39, 4, 41, 0, 19, 29, 44, 43, 44, 21, 34, 39, 23, 7, 1, 24, 30, 34, 40, 26, 28, 11, 44, 19, 48, 12, 5, 10, 2, 21, 0, 24, 8, 44, 36, 20, 6, 2, 4, 21, 14, 6, 47, 31, 23, 29, 4, 36] and you have at most 10 buy-sell trades allowed. What is your maximum profit?
To tackle this problem, I would first break down the problem. Here, it is asking for the maximum profit for at most n stock buy-sell stock trades. I will split it into sub-problems where I can find the maximum profit for exactly n buy-sell trades, and later I can search for the max among them.
So, the sub-problem is now to find the maximum profit given N-day forecast where I need to trade exactly n times. Since each trade is either buy or sell, I will once again split this sub-problem into sub-sub-problem as follows:
B(x, N, n): given N-day forecast of prices x, find the maximum cash after exactly n-1 buy-sell trades and another buy by the Nth day.
S(x, N, n): given N-day forecast of prices x, find the maximum cash after exactly n buy-sell trades by the Nth day.
With these functions, it is not too difficult to come up with a simple recursion relationship. Perhaps it is easy to see this from Python code below:
So, that is the recursive part of dynamic programming. Now, we need to deal with the memoization part. Note that with the recursion above, the performance will be very slow, since the number of recursive calls exponentially grows, where they are called with the same parameters multiple times. While we can store the results for all possible parameters, this will take up too much memory ~ O(N*N). A better way is to start from N = 1 and store all possible values for n, and increment N by 1 each time. This requires O(N) space.
It is probably better to explain in code below:
To run it:
$ python dp2.py 10
[4, 1, 4, 6, 2, 7, 4, 9, 7, 4]
[0, 8, 12, 15, 12, 6]
That is, given 10-day stock price [4, 1, 4, 6, 2, 7, 4, 9, 7, 4], the most profit you can make by trading up to 5 buy-sell trades using aforementioned rule is 0, 8, 12, 15, 12, and 6. Now, to find the answer to the original question, we simply take the maximum of the array. Given 2 maximum buy-sell trades, the most profit one can make is 12.
By the way, the problem become trivial if maximum allowed trade is N/2, in which case one simply buys at local minimum and sells at local maximum. Hence, this algorithm shines when n is less than N/2.
No comments:
Post a Comment