https://www.acmicpc.net/problem/1309
initial
Look how disorganised my workings are for trying to find the DP pattern. Wait till u see the model solution's working.
You can argue that you just need the dp value for given n to find out the pattern and formula but really think clearly like the coin problem and how previous patterns add up to the current pattern.
solution
https://great-park.tistory.com/131
Look how organised this is. We are deciding whether to add a lion or not to the previous pattern to form current pattern for a given n. This way, it is much better than arbitrarily trying to find out all the patterns.
And the recursive formula can be deduced as dp[i] = 2*dp[i-1] + dp[i-2]. I did a whole shit show of trying to find out the pattern, as you can see in the images above but really if I think it is going the wrong way (prob cuz it is overcomplicated) then take 10 steps back and start fresh from the dp values and try deducing a new pattern.
solution
n time and space
