Memoization gave me TLE on 144th testcase and simple DP gave TLE on 153rd testcase. I was confident of solving this myself but this problem humbled me. The optimization is so smart!
My intuition for the left/right optimization: Let's say the previous row is [A, B, C, D]. We only consider elements from left-to-right for now. The maximum value for the first element in the current row is: max(A) == A The maximum value for the second element in the current row is: max(A - 1, B) == max(A- 1, B) The maximum value for the third element in the current row is: max(A - 2, B - 1, C) == max(max(A - 1, B) - 1, C) The maximum value for the forth element in the current row is: max(A - 3, B - 2, C - 1, D) == max(max(max(A - 1, B) - 1, C) - 1, D) So it's a rolling max(prev_max - 1, element_right_above). And similarly do right-to-left for the second half.
i knew it was a DP problem the second I read the problem and constraints but I really got humbled when Memoization failed, tried fixing it but did not work, came straight here, Thanks neetcode!
Probably not, but now when you get to a similar problem you'll know how to solve and that's what matter. What we can get from this problem is the idea from left- right and that some problems have double nested dp
It's a bit of a stretch to call the solution DP. It's more of a clever precalculation. The features of the solution lacks the usual features of DP like exploring combinations. I get that is encoded in the precalculation hence why I think it shouldn't be tagged as dynamic programming.
Thank you for such a great explanation. ❤ I couldnt able to identify that this can be solved using dp 😢 How to identity dp can be used to problems I used different approach (i think its greedy) but it was wrong, my solution is.. taking max val in a row and keeping track of max id and using this to find max val in next row and summing up.. got failed bcoz elements in a row are not always unique.
For the life of me, I cant figure it out how to optimize the get max from previous row part. Thank you so much for the explaination. 2 questions though: - At which point does the thought of 6:00 occurred to you that it is impossible? Did it come at you intuitively or you somehow proved it using quick maff? I too thought that it is impossible at first, but the thought of looping all cells in the prev rows to pick one was too "bruteforce" and I thought it would result in TLE, so I discarded that thoughts. - How would you know that looping each row twice (thrice to build the actual dp) would not result in TLE? I did come up with the thoughts of check max for each current_element but the thought of looping all the rows made me discarded that approach
I'm not sure if my take is correct, but here's how i understood it, left and right feels like a greedy solution more than a dp solution where you take the max between the previous and current utility (val - cost) where the current col has a cost of 0 and the relative cost is the dist from the current col, this is because you cant really reuse the calculations for any of the cols because each cols despite having the same utility have a relative cost
Let's say the previous row is [A, B, C, D]. We only consider elements from left to right for now. The maximum value for the first element in the current row is: max(A) == A The maximum value for the second element in the current row is: max(A - 1, B) == max(A- 1, B) The maximum value for the third element in the current row is: max(A - 2, B - 1, C) == max(max(A - 1, B) - 1, C) The maximum value for the forth element in the current row is: max(A - 3, B - 2, C - 1, D) == max(max(max(A - 1, B) - 1, C) - 1, D) So it's rolling max(prev_max - 1, element right above). And similarly do right to left for the second half.
This kind of problems is the problems where if your mind don't randomly send a hint you just can't rationalize until a solution, but with enough practice, you can increase the chance of the mind sending a hint but it's always not 100%
i figured out another approach using heaps, which is slower (2460ms), but still passed. Time complexity mlogm * n. class Solution: def maxPoints(self, points: List[List[int]]) -> int: height = len(points) width = len(points[0]) ans = [[0] * width] + [[None] * width for _ in range(height)] for r in range(height): heap = [(-points[r][i] + ans[r][i], i) for i in range(width)] heapq.heapify(heap) while heap: n, i = heapq.heappop(heap) if ans[r+1][i] is None: ans[r+1][i] = n if i > 0 and ans[r+1][i-1] is None: heapq.heappush(heap, (n+1, i-1)) if i < width -1 and ans[r+1][i+1] is None: heapq.heappush(heap, (n+1, i+1)) return -min(ans[-1])
