I'm attempting to solve the following problem:
Balls are falling from the sky. We know at which location (on a straight line) will each ball drop, and we know the time (in seconds) at which will the ball reach the ground. We are trying to catch them into a ball net, which we can move left or right, but each movement costs 1 second. The initial position of a ballnet is always on the left (position 0). We are allowed to > drop (not catch) $k$ number of balls.
What is the highest score we can achieve?
My first attempt at solving this was a greedy algorithm:
if the |next ball position - current position of the ball net| > (time of the next ball - current time) then attempts++ if attempts>$k$ print game over else current ball net position = next ball position current time = time of the next ball score++
however my algorithm doesn't take into consideration that sometimes it's better to sacrifice some number of balls in order to reach a higher score in the long run. This needs an approach via dynamic programming, I think.
Is this problem a known one so I can find some help? Could you help me with this problem? I can solve this in a greedy way, however I am failing to do it dynamically.