Maximum Number of Points with Cost - Leetcode 1937 - Python

Показать описание

0:00 - Read the problem
0:30 - Drawing Explanation
11:02 - Coding Explanation

leetcode 1937

#neetcode #leetcode #python

NeetCodeIO

Рекомендации по теме

Комментарии

at this point leetcode is testing my willpower rather than my coding knowledge

hardiksrivastava

The idea for optimizing from O(m*n^2) to O(m*n) is so smart....

chien-yucode

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!

ParodyCSEDept

small nitpick on 10:25 dp[2] is 7 not 8

kalmyk

At this point its not dynamic programming anymore, its double penetration

tuandino

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.

deep.space.

this dp monster seems to have no bounds to its power😢😢

nptelpunith

This it tough with that double DP aspect to it, feels like a Hard problem IMO. Thanks for the awesome explanation as always man

jackgordley

Everything up to left/right was quite intuitive. I understand what you did and why. I don't understand the intuition. That's the frustrating part.

Neuromancer_k

took a two week break and came back to this never quitting lc again :( skill gapped

pratyushthakur

10:22 Should be 1+max(6, 4)=7 <= friendly reminder for viewers

DNKF

wow. didn't know that solution so simple! incredible!

JamesBond-mqpd

it would have been be good if you could share your thought process/intuition.

gui-codes

Damn, looked at various solutions, but yours is very easy to understand

venkataraman

Memoization solution gave me the tle is horryfying.

kapilkhandelwal

How do u come out with this? Is it try and error ? Or just experience, cause i would never would have think of computing it left and right.

doctor_cats

will solving enough dp problems help me come up with the left and right array intuitively? I was able to do the brute force dp but not thsi one <(

vedanti

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!

oneplusgeek

Thanks for the consistent videos mate.!❤I appreciate your efforts

deshpanderamakrishna

Thanks for this video. This will be my first time solving DP problem.

vupdates

Maximum Number of Points with Cost - Leetcode 1937 - Python

Maximum Number of Points with Cost - Leetcode 1937 - Python

Leetcode 1937 Maximum Number of Points with Cost

Maximum Number of Points with Cost | Detailed Explanation | Leetcode 1937 | codestorywithMIK

Leetcode- Maximum Number of Points with Cost

1937. Maximum Number of Points with Cost | Dynamic Programming | Leetcode Daily Challenge | JAVA

Leetcode 1937 Maximum Number of Points with Cost|CPP|DP|Interview Problem

LeetCode 1937. Maximum Number of Points with Cost

1937. Maximum Number of Points with Cost. Leetcode.

𝑷𝑶𝑰𝑵𝗧 𝗢𝗙 𝗜𝗡𝗙𝗟𝗘𝗖𝗧𝗜𝗢𝗡 | 𝗺𝗶𝗻𝗶𝗺𝘂𝗺 𝘃𝗮𝗹𝘂𝗲 | 𝗺𝗮𝘅𝗶𝗺𝘂𝗺 𝘃𝗮𝗹𝘂𝗲 | 2𝗻𝗱 𝗱𝗲𝗿𝗶𝘃𝗮𝘁𝗶𝘃𝗲𝘀 𝘁𝗲𝘀𝘁 | 𝗞𝗣𝗞 𝗯𝗼𝗮𝗿𝗱...

1937. Maximum Number of Points with Cost | LeetCode Medium

LeetCode 1937 - Maximum Number of Points With Cost - Java

Maximum Number of Visible Points Leetcode 1610 Solution using Sliding Window and Polar Coordinates

1937. Maximum Number of Points with Cost, LeetCode, Java

1937. Maximum Number of Points with Cost (Leetcode Medium)

Maximum Number Of Points With Cost - LeetCode 1937 | C++

Maximum Number of Points with Cost

Maximum Number of Points Possible in vib-ribbon (21,591,115)

1937. Maximum Number of Points with Cost || leetcode medium || potd

Max Points on a Line || Find the maximum number of points that lie on the same straight line

Leetcode 2503: Maximum Number of Points From Grid Queries

1937. Maximum Number of Points with Cost - Day 17/31 Leetcode August Challenge

LeetCode 1610. Maximum Number of Visible Points

1610. Maximum Number of Visible Points (Leetcode Medium)

Maximum number of points with cost Leetcode Weekly Contest 250 Solution very easy in C++