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}$$$.
Solutionlet $$$f_n$$$ be the solution of $$$n$$$, now let's backtrace,
$$$n$$$ comes -> $$$n-1$$$ won't come, but $$$n-2$$$ can be in the subset, but necessarily isn't so $$$f_{n-2}$$$
$$$n$$$ doesn't come -> $$$n-1$$$ can be so $$$f_{n-1}$$$
giving us $$$f_n = f_{n-1} + f_{n-2}$$$
Question. 2 Same as Question 1 but should have at least 2 elements in between them
Solutionlet $$$f_n$$$ be the solution of $$$n$$$, now let's backtrace,
$$$n$$$ comes -> $$$n-1$$$ won't come, neither $$$n-2$$$ will, but $$$n-3$$$ can be in the subset, but necessarily isn't so $$$f_{n-3}$$$
$$$n$$$ doesn't come -> $$$n-1$$$ can be so $$$f_{n-1}$$$
giving us $$$f_n = f_{n-1} + f_{n-3}$$$
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$$$.
SolutionSo the current string with length $$$n$$$ either was another string with length $$$n-1$$$ with the b at the end,
or was $$$n-2$$$ with ba at the end or $$$n-3$$$ with baa at the end. So $$$a_n = a_{n-1} + a_{n-2} + a_{n-3}$$$
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
Полный текст и комментарии »