### bgopc's blog

By bgopc, history, 6 months ago,

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

• -33

 » 6 months ago, # |   0 hi.Thank You