The solution for this problem states that it follows the relation: S(n)=S(n−1)+S(n−2)+S(n−4)
I’m not able to understand how did we arrive at this relation. The visualization too depicts the relation being applied. Could someone let me know how one would explain arriving at this relation? what is the thought process behind it?
I tried applying the logic of ‘coin change problem’ here but it does not seem to fit the relation here. Thanks.
Last night I banged my head against the wall trying to figure it out and I could finally realize why it works. First thing you need to know is that is all about deciding whether a combination of scores is valid. E.g,
If n would be 4 you could do
1 | 1 | 1 | 1 |
1 | 1 | 2 |
1 | 2 | 1 |
2 | 1 | 1 |
2 | 2
4
That’s 6 ways of adding 4, so far so good. You could start thinking in combinatorics and permutations (which is a valid answer) but there is an easier way to do it, and is by thinking the problem as a decisions one,
The question here is, how you can generate that table?
If you pay attention to the first column of the table you can pick 1, 2 or 4, right? The value you choose will be substracted from n, that is.
s(n) = s(n-1) + s(n-2) + s(n-4)
s(4) = s(3) + s(2) + s(0)
Let’s start by choosing score 1.
1 | 1 | 1 | 1 |
1 | 1 | 2 |
1 | 2 | 1 |
2 | 1 | 1 |
2 | 2
4
now
s(3) = s(2) + s(1) + s(-1)
let’s choose 1 again
1 | 1 | 1 | 1 |
1 | 1 | 2 |
1 | 2 | 1 |
2 | 1 | 1 |
2 | 2
4
if we go deep choosing ones, then we will eventually get
s(1) = s(0) + s(-1) + s(-3)
but hey, you can’t get s(-1) and s(-3), those are all zeroes. However, s(0) it’s a possibility since we will consider it a base case with value 1. That means, we went from n to 0 by substracting only ones.
1 | 1 | 1 | 1 |
1 | 1 | 2 |
1 | 2 | 1 |
2 | 1 | 1 |
2 | 2
4
Since s(1) is now 1 we can replace,
s(2) = s(1) + s(0) + s(-2)
s(2) = 1 + s(0) + s(-2) // Here we will include the decision of adding a value with score 2
s(2) = 1+ 1 + s(-2) // But we already have s(0) so we just replace
s(2) = 2 + s(-2) // Note you can’t add a score of 4, because s(-2) is 0
s(2) = 2
1 | 1 | 1 | 1 |
1 | 1 | 2 |
1 | 2 | 1 |
2 | 1 | 1 |
2 | 2
4
s(3) = s(2) + s(1) + s(-1)
s(3) = 2 + 1 + 0 // We are also considering the cases when we choose 2 in the second choice
s(3) = 3
1 | 1 | 1 | 1 |
1 | 1 | 2 |
1 | 2 | 1 |
2 | 1 | 1 |
2 | 2
4
s(4) = s(3) + s(2) + s(0)
s(4) = 3 + 2 + s(0) // We are also considering now the cases with 2 in the first choice
1 | 1 | 1 | 1 |
1 | 1 | 2 |
1 | 2 | 1 |
2 | 1 | 1 |
2 | 2
4
s(4) = 5 + s(0)
s(4) = 5 + 1 // We are also considering now the cases with 4 in the first choice
1 | 1 | 1 | 1 |
1 | 1 | 2 |
1 | 2 | 1 |
2 | 1 | 1 |
2 | 2
4
s(4) = 6
I hope it gets clear for you.
Hello Matias,
Thanks for your explanation but i don’t understand what you mean by pick 1