How to get used to dp thinking

Revision en1, by bgopc, 2024-02-10 17:55:05

Hello, In this blog, I've tried to share my opinion on how to get good at dp problems, so stick to the end
in my opinion, dp is 85% thinking on paper, 10% thinking in your brain and 5% implementation.
so if you approach a dp problem always have pencil and paper and USE THEM another thing is just solving the DP problems in combinatorics.
What do I mean?

Question. 1 Given $n$, generate the set $s$ s.t $s = {1, 2, 3, 4, ..., n-1, n}$ then
count the number of subsets, where those elements in the set have at least 1 element in between them;
for example, $n = 8$ then $s = {1,2,3,4,5,6,7,8}$, one valid subset would be ${1,4,8}$.

Solution

Question. 2 Same as Question 1 but should have at least 2 elements in between them

Solution

Question. 3 Same as Question 1, Let's stop it
Let $a_n$ be the number of binary strings with ab, s. t no three consecutive characters are a.
find a recursive formula for $a_n$.

Solution

Since the problems I've are in Persian and translating them would be a pain, Message me and I'll send them to you if you want but the translation is on you

Hope this Helped

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 bgopc 2024-02-10 17:55:05 2026 Initial revision (published)