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:

1. The idea of updating dp in two directions (Sending a Sequence Over the Network)
2. Keeping our states for matching subsequences (Easy Problem)
3. Importance of ordering in updating DP (Gargari and Permutations)
4. Keeping max values to optimize DP (Choosing Balls)
5. 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.

Easy Problem

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.

Gargari and Permutations

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).

Choosing Balls

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.

Pigs and Palindromes

Let me know your opinions! Together we can make the livestreams better.