Introduction
It is my favorite weekly contest. I solved two algorithms, but I came out the third algorithm using dynamic programming solution. I could not complete the third on since I only had 10 minutes left to work on the solution.
Case study
I should be able to complete the third algorithm dynamic programming in less than 10 minutes. But I have not written a dynamic programming solution for long time. I wrote one solution after the contest using List<int> to help, but the first one is so messy with redundant if/ else and isEqual discussion.
I like to share the links of my discussion posts.
Algorithm 1 is here.
Algorithm 2 is here.
Algorithm 3 is here.
I stuck on first easy level algorithm, as shown in the above image, I spent 41 minutes to play with submission and test cases, and then I made it work.
I did not have time to read the fourth algorithm at all. I need to work on my reading skills. Sometimes I have to think carefully before I write the code, I had to hack the code and then figured out what was asking. Life is tough to play weekly contest.
Algorithms 3 is a dynamic programming. I have to learn some tip to avoid the edge case. I also asked question about the most popular post the question. The post is here, the question is the following, I did ask some one before more than a year ago, I also wrote a blog about it.
May I ask you how to argue the following statement is correct?
dp[i][j] = 1 + dp[i - 1][j - 1];
The above statement is based on the fact that dp[i - 1][j] <= 1 + dp[i - 1][j - 1] and dp[i][j -1] <= 1 + dp[i -1][j - 1]. How to reason those two formulas?
Follow up
May 3, 2019
I got response back from the author.
No comments:
Post a Comment