Click here to see the full article post
Hi. You insert a P before the ---LLL in order to make the f[n-3] string rewardable. I don't understand this. If the f[n-3] string "bleeding" into the L or LL of the ---LLL makes the f[n-3] string unrewardable, then why doesn't the first of the four cases (---LPL) have the same issue, where an f[n-5] string ending in LL would also "bleed" into the last characters, creating ---LLLPL?
@elle First Fix 'P' at last position (----P), this will result f[n-1]. Now fix 'L' at the last position, out of all valid f[n-1] strings, only strings ending with PLL should not be considered as it will lead to --PLLL strings which is not valid. Thus it results in f[n-1]-f[n-4] and total of 2f[n-1]-f[n-4]. Please let me know if you still have some question?
Thanks for your reply. Why fix an additional P to make ---PLLL? Isn't ---LLLL also invalid? The final recurrence relation is absolutely correct, but I'm not sure this is the correct explanation. I can explain a simpler way to get to 2f[n-1]-f[n-4] but first I would like to understand yours. By the way, that's a typo in the graphic, writing "N" for the right branch instead of "P", right?
@elle This is because, we need to consider only those strings which are rewardable at the length (n-3) but become unrewardable at a length(n-1)(for left branch ). Only the strings ending with a P at length (n-3) and ending with PLL of the left branch at length (n-1) follow this criteria. Could you please share your simpler explanation?
Right. So consider the 1st of the 4 branches: [n-3]LPL. A string like PPPPPPPPPPPPPPPLLLPL would be rewardable at [n-3] but fail at [n-1], would it not? That was my original question: Under your approach, why doesn't the 1st branch get considered as a "rewardable at [n-3] but unrewardable at [n-1]" case? Maybe your criterion is more specific but not fully stated; I would like to understand that part.
The simpler way, IMHO, and compliments to N. Shade at math.stackexchange.com, is to consider the cases (a) ------P, (b) ------PL, and (c) ------PLL. A minute of thought will reveal that these are mutually exclusive. It's also realized that going further, e.g. (d) ------PLLL, becomes useless because the string will always be unrewardable. So the whole of f[n] may be summarized by (a) + (b) + (c), in other words, f[n] = f[n-1] + f[n-2] + f[n-3]. This means also that f[n-1] = f[n-2] + f[n-3] + f[n-4]. If you subtract the latter from the former to cancel out the f[n-2] and f[n-3] cases, then you are left with f[n] = 2 f[n-1] - f[n-4].
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.