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].
Space complexity of brute force approach is wrong it cannot be O(n^n) unless you store all the entries, which you are not doing.
Space complexity will remain O(n) which is equal to depth of the tree.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.