Hi,
As always, we have topic streams on Fridays from 12-14 GMT. Today was the second topic stream on Dynamic Programming. Here are the topics covered in this livestream:
- The idea of updating dp in two directions (Sending a Sequence Over the Network)
- Keeping our states for matching subsequences (Easy Problem)
- Importance of ordering in updating DP (Gargari and Permutations)
- Keeping max values to optimize DP (Choosing Balls)
- Memory optimization and moving in two directions (Pigs and Palindromes)
I will write the highlights of the livestream here, embedding specific parts of the videos so you can easily watch the sections you’re interested in. You can ask questions about any part here, on YouTube, or in our Telegram Channel. The main discussion thread is in our Telegram Channel.
Updating DP in two directions
In DP problems, sometimes we calculate dp[i] when we reach i by using smaller instances (j < i). Other times, when we reach i, we assume that we already have dp[i] and update the larger instances (j > i). In some cases, we can do both simultaneously.
Sending a Sequence Over the Network
Keeping our states for matching subsequences
In this problem, we want to remove certain characters to ensure that the string "hard" does not appear as a subsequence in our string. We explore how to maintain states that track how many characters of "hard" have already been matched and how this helps us solve the problem efficiently.
Importance of ordering in updating DP
In this problem, we see how the order of calculating DP values can be important and how to find the right ordering.
Keeping max values to optimize DP
In this problem, we first come up with an O(n^2) DP solution. Then we optimize it by keeping track of the two maximum DP values. This way, we can update dp[i] in O(1) instead of O(n).
Memory optimization and moving in two directions
Here, in addition to the idea of considering the diagonals of a grid and maintaining our states, we see how we can optimize memory by taking one of the dimensions modulo 2.
Let me know your opinions! Together we can make the livestreams better.