Hi,

Today, I had my first topic stream on Dynamic Programming. The stream lasted for two hours, and this was the plan for the first livestream:

1. Start with the basics of Dynamic Programming: the logic behind it and when to apply it.
2. Boredom — difficulty 1500
3. Consecutive Subsequence — difficulty 1700
4. Red-Green Tower — difficulty 2000
5. Winter is here — difficulty 2200

I will write the highlights of the livestream here, while embedding the specific parts of the videos so that you can easily watch the parts you want. You can ask questions about any part here, on YouTube, or in our Telegram Channel. The main discussion thread is in our Telegram Channel.

The Basics of Dynamic Programming

In this part, I talk about what Dynamic Programming is and why we might want to use it. I explain how to figure out if we can apply DP to a problem. Of course, as an example, I discuss the Fibonacci sequence—who doesn’t use Fibonacci when explaining DP? I tried to skip unnecessary details and keep the focus on the most important points.

455A — Boredom

This problem helps to build intuition on how DP works. It’s an example of defining states and solving the main problem using those states. In this case, we define dp[i] as the answer when considering only the numbers from 1 to i and ignoring the rest.

977F — Consecutive Subsequence

This is another problem that helps with the idea of defining subproblems as the different cases that contribute to our final answer. Here, we define dp[i] as the answer if the last chosen number in our subsequence is i.

478D — Red-Green Towers

This problem combines a greedy algorithm to find the best value for h and defines subproblems like (i, j). This states how many ways we can have a pyramid of height i using j red blocks.

839D — Winter is here

This one features number theory. We want to find the value of dp[x] as the number of possible subsets whose GCD is x. To do this, we first find the number of subsets where one of their common divisors (not necessarily the maximum one) is x. From there, we determine the number of subsets whose GCD is x.

Let me know your opinions! This is your livestream, and together we can make it better.