Good morning! Hope you had a great weekend. The weekend was not too exiting for my wife and me. We did replenish our freezers for the next few months. I believe we have enough supplies to last us through a good part of spring 2022.
We decided to cook some ribs in the oven. We have done this several times, but due to the fact that my wife is not too fond of such delicacy we have not cooked them in about three years. I pulled the ribs from one of the freezers and put it in a refrigerator for three days. On Friday evening I took them out of the fridge and they were still partly frozen.
On Saturday morning after breakfast I rubbed some salt and pepper on the ribs. Like I mentioned, she is not too fond of ribs or BBQ sauce. I wanted to add some that we got at Trader Joe’s a couple weeks ago. I ended using the sauce on my dish. My wife used an Asian sauce which went very well with ribs. We also bought that sauce at Trader Joe’s.
I was going to set the oven at no more than 300F, but my wife suggested 325F to get them done faster. The ribs went in around 07:00 AM. After showering and getting dressed, I went down to my office for a 2-hour block.
Later that morning my wife and I sat down for a cup of triple espresso. We chatted and decided to get a couple items at a specialty grocery store in St. Paul. We turned off the oven and headed out. In retrospect, we should have removed the ribs from the oven. We had lunch around 01:00 PM and the ribs got a little dry for my taste. We had them with brown rice and black beans. We both enjoyed them, but once a year is enough. The taste is very unique like turkey. We have turkey on Thanksgiving Day and perhaps Christmas. I guess most people do the same in this part of the country.
On a separate note, I ran into the article Was Our Universe Created in a Laboratory? by Avi Loeb published on Scientific American on October 15, 2021. The article starts with the word “Opinion” which puts it into perspective.
I am not going to get into the implications of the ideas in the article. My parents taught me never to discuss religion, money or sex. Such subjects are very opinionated and it is hard to get a general consensus. That said; here we are talking about the article. The reason for me to bring it up is due to the fact that for the past three decades or more, when my wife and I talk in private, I have described to her the idea of multiple universes generated by beings more advanced than us. In such universes there are some actual beings and many artifacts. The idea behind is to study scenarios that in general fall outside our comprehension and interests.
I have to tell you that as soon as I read the article, I ran to my wife to tell her about it. We both thought it was very interesting.
In my thoughts and opinion, the article does not exclude a superior being that is above all levels. It just puts such being above the more advanced civilization(s) that at this point are able to generate universes.
I will try to contact the author of the article and let him know that I really enjoyed reading it. After an hour or so of sending my message to the author, I received a reply. Thanks.
OK, let’s now get to the main subject of this post.
While doing some research on-line, I ran into the article Dynamic programming is simple by omgitspavel (hopefully not his actual name). The article presents a process to deal with most (90% according to the author) Dynamic programming problems. We have dealt with a different approach that covered multiple posts in this blog i.e., Can Sum – Tabulation and Grid Traveler – Tabulation among others.
Please read the article and try solving the LeetCode 714 Best Time to Buy and Sell Stock with Transaction Fee problem rated Medium.
The author uses Python in his examples. We will start using Python in this blog in the near future. At this time we will use Java and the VSCode IDE on a Windows computer. Windows 11 is already available for general release. You need to make sure that your computer has TPM 2.0 hardware support. Some of my machines do, other do not. Moving forward will have to purchase a couple new machines.
I read the article in question and followed while attempting to solve the problem at hand. The process seems very promising. The author suggests that it should take between 15 – 20 DP problems to master the new method. I will try solving a few DP problems in the next few posts.
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). Constraints: o 1 <= prices.length <= 5 * 104 o 1 <= prices[i] < 5 * 104 o 0 <= fee < 5 * 104 Hint: Consider the first K stock prices. At the end, the only legal states are that you don't own a share of stock, or that you do. Calculate the most profit you could have under each of these two cases.
We have seen variations of this problem in this post. According to the author of the paper, we are supposed to forget what we have learned on DP. So let’s not look at past DP problems and start fresh.
In this problem we are given an int[] with the prices for a particular stock. The prices in the array are ordered in consecutive days starting with day 0. In addition we are given a transaction fee used for each transaction.
What we need to determine is the `maximum profit` we can achieve during the specified period with the specified prices. This is starting to sound like Coinbase but with a stock instead of a cryptocurrency.
public int maxProfit(int[] prices, int fee) {
}
The signature for the function in question is simple. We are provided with a list of prices in a time period and the transaction fee which seems to apply when you buy and when you sell. Not bad is you are a broker!
Since we are going to develop the solution on our machine not using the on-line IDE provided by LeetCode, we will have to develop a test scaffold (NOT PART OF THE SOLUTION) which will read the two input lines, populate the arguments used to call the function of interest, call the function of interest and display the result.
1,3,7,5,10,3 3 main <<< prices: [1, 3, 7, 5, 10, 3] main <<< fee: 3 main <<< Output: 6 main <<< Output: 6 maxProfit <<< day: 1 price: 3 cash: 0 hold: -1 maxProfit <<< day: 2 price: 7 cash: 3 hold: -1 maxProfit <<< day: 3 price: 5 cash: 3 hold: -1 maxProfit <<< day: 4 price: 10 cash: 6 hold: -1 maxProfit <<< day: 5 price: 3 cash: 6 hold: 3 main <<< Output: 6 9,7,5,3 2 main <<< prices: [9, 7, 5, 3] main <<< fee: 2 main <<< Output: 0 main <<< Output: 0 maxProfit <<< day: 1 price: 7 cash: 0 hold: -7 maxProfit <<< day: 2 price: 5 cash: 0 hold: -5 maxProfit <<< day: 3 price: 3 cash: 0 hold: -3 main <<< Output: 0 1,3,2,8,4,9 2 main <<< prices: [1, 3, 2, 8, 4, 9] main <<< fee: 2 main <<< Output: 8 main <<< Output: 8 maxProfit <<< day: 1 price: 3 cash: 0 hold: -1 maxProfit <<< day: 2 price: 2 cash: 0 hold: -1 maxProfit <<< day: 3 price: 8 cash: 5 hold: -1 maxProfit <<< day: 4 price: 4 cash: 5 hold: 1 maxProfit <<< day: 5 price: 9 cash: 8 hold: 1 main <<< Output: 8
We are provided two input lines. The first holds the prices of the stock for the specified number of days. The second line holds the transaction fee which applies to each buy and sell transaction.
Each of the test cases seems to implement three solutions. The last implementation seems to display some values that should help up follow the last implementation.
I did follow the process described in the article. I agree that one needs to solve a few DP problems before mastering the specified approach.
/**
* Test scaffold
* NOT PART OF SOLUTION
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read prices int[] array ****
int[] prices = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read int fee ****
int fee = Integer.parseInt(br.readLine().trim());
// *** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< prices: " + Arrays.toString(prices));
System.out.println("main <<< fee: " + fee);
// **** call function of interest and display result ****
System.out.println("main <<< Output: " + maxProfitNoMemo(prices, fee));
// **** call function of interest and display result ****
System.out.println("main <<< Output: " + maxProfitBF(prices, fee));
// **** call function of interest and display result ****
System.out.println("main <<< Output: " + maxProfit(prices, fee));
}
Our test code reads the two input lines, populates a couple variables, calls three different implementations of the solution and displays the results.
/**
* Find the maximum profit you can achieve.
* Recursion entry point.
* Does not make use of memoization!
*
* 19 / 44 test cases passed.
* Status: Time Limit Exceeded
*/
static public int maxProfitNoMemo(int[] prices, int fee) {
return dp(prices, fee, 0, false);
}
This is one of the early implementations. The article shows different implementations that rest on each other. As you follow the process your solutions seem to become faster. As you can see in this case, the code was able to pass all the test cases but timed out when the code was submitted.
/**
* Recursive dynamic programming function.
* No memoization!
*/
static private int dp(int[] prices, int fee, int day, boolean bought) {
// **** base case ****
if (day >= prices.length) return 0;
// **** initialization ****
int maxProfit = 0;
// **** buy stock state ****
if (!bought)
maxProfit = Math.max(maxProfit, dp(prices, fee, day + 1, true) - prices[day] - fee);
// **** sell stock state ****
else
maxProfit = Math.max(maxProfit, dp(prices, fee, day + 1, false) + prices[day]);
// **** do nothing state ****
maxProfit = Math.max(maxProfit, dp(prices, fee, day + 1, bought));
// **** return the max profit ****
return maxProfit;
}
We start the recursive function by stating the base case. We have a set of days in which we can buy, sell or do nothing with the stock. Make sure you agree with these three possible states before starting to code your solution.
We then initialize a variable which will hold the maximum profit that we can obtain.
The article describes how you can advance from the three states to what you see here in this implementation. You will be able to add arguments to the call based on the need of the problem. The process is quite good and relatively easy to follow.
The problem at this time is that the code, if submitted, times out. In general this is to be expected when using DP and no memoization.
// **** memoization ****
static private HashMap<String, Integer> memo = null;
In this case we will implement memoization with a hash map. The key will be a combination of the variables `day` and `bought` and the value will be the `maxProfit`. We will combine the int `day` and the Boolean `bought` into a string.
/**
* Find the maximum profit you can achieve.
* Brute force approach.
* Recursion entry point.
*
* 44 / 44 test cases passed.
* Status: Accepted
* Runtime: 682 ms
* Memory Usage: 475.6 MB
*/
static public int maxProfitBF(int[] prices, int fee) {
// **** initialize memoization ****
memo = new HashMap<>();
// **** start recursion and return result ****
return dpBF(prices, fee, 0, false);
}
This is the entry point for the implementation using memoization.
We initialize the hash map and then start recursion.
The maximum profit will be returned by the recursive process.
/**
* Recursive dynamic programming function.
* Started with brute force approach and ended
* with DP with memoization solution.
*/
static private int dpBF(int[] prices, int fee, int day, Boolean bought) {
// **** base case ****
if (day >= prices.length) return 0;
// **** initialization ****
int maxProfit = 0;
// **** build the key ****
String key = "" + day + " " + (bought ? "1" : "0");
// **** check memo ****
if (memo.containsKey(key)) return memo.get(key);
// **** buy stock (if needed) ****
if (!bought)
maxProfit = Math.max(maxProfit, dpBF(prices, fee, day + 1, true) - prices[day] - fee);
// **** sell stock (if needed) ****
else
maxProfit = Math.max(maxProfit, dpBF(prices, fee, day + 1, false) + prices[day]);
// **** do nothing ****
maxProfit = Math.max(maxProfit, dpBF(prices, fee, day + 1, bought));
// **** update memo ****
memo.putIfAbsent(key, maxProfit);
// **** return the max profit ****
return maxProfit;
}
This implementation is quite similar that the previous one. There are two differences. After we generate the value for the `key`, we check in the hash map for the associated key-value pair. If the key-value pair is found, we return the value which represents the associated `maxProfit`.
If we do not find the key-value pair, we process the recursive calls and when we have computed the new maxProfit and before we exit the function, we update the memoization with the new key-value pair.
This is typical processing of memoization.
As you can verify in the maxProfitBF() function, the code was accepted by LeetCode but was quite marginal.
At some point I continued to move forward but decided to try a different approach. I would assume that if continuing with the specified process in the article, one might find a different solution.
/**
* Find the maximum profit you can achieve.
* Iterative approach.
*
* 44 / 44 test cases passed.
* Status: Accepted
* Runtime: 3 ms
* Memory Usage: 48.2 MB
*
* Runtime: O(n) - Space O(1)
*/
static public int maxProfit(int[] prices, int fee) {
// **** initialization ****
int hold = -prices[0]; // buy stock
int cash = 0; // do not buy stock
// **** loop for each day - O(n) ****
for (int day = 1; day < prices.length; day++) {
// **** sell stock ****
cash = Math.max(cash, hold + prices[day] - fee);
// **** hold stock ****
hold = Math.max(hold, cash - prices[day]);
// ???? ????
System.out.println( "maxProfit <<< day: " + day + " price: " + prices[day] +
" cash: " + cash + " hold: " + hold);
}
// **** return cash at hand (max profit) ****
return cash;
}
The approach here is somewhat different.
In this case we process the days in the prices array and determine the amount of cash we have per day. We consider two cases. In one we sell stock and in the other we hold to the stock. When all is said and done we return the cash on hand which as you should be able to follow on the print statements, provides the maximum profit.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John