edgelord dp frog problem

zbig.py

# your code goes here

# "The frog Zbigniew jumps on a number axis. 
# It has to get from 0 to n - 1, jumping only in the positive direction. 
# The jump from the number 'i' to number 'j' ( j > i ) costs Zbigniew ( j - i ) units of energy, 
# but lucky him, on certain slots - even on the zeroth - exist snacks with a certain energy value (the energy value of a snack is added to the current energy of Zbigniew).
# Implement a function zbigniew(A), which gets on input an array A, with the lenght len(A) = n, 
# in which each slot contains the energy value of the  laying snack. 
# The function should output the minimal amount of jumps needed to get from 0 to n-1 or -1 if it isn't possible.
# Tip: You should consider the function f(i, y) returning the minimal amount of jumps to get to a slot having exactly y energy left.
# Example: A = [2, 2, 1, 0, 0, 0] output: 3
# A = [4, 5, 2, 4, 1, 2, 1, 0] output: 2

import sys
A = list(map(int, input().split()))

def zbig(A): # MINIMAL NO. OF JUMPS to get to the end slot
    n = len(A)
    
    memo = [ [-2] * sum(A) for _ in range(n) ] # max theoretical energy (which is not true, because you have to subtract energy by one when jumping 1 slot)
    def f(start, energy):
        
        # let's say energy is 2 and start is 0 target is 6
        # possible slots i can jump to are 1 and 2

        if energy < 0:
            return -1
        elif start == (n-1):
            return 0

        if memo[start][energy] > -2:
            return memo[start][energy]

        e = energy + A[start]
        ans = sys.maxsize
        for i in range(start+1, min(start + e + 1, n)):
            jumps = f(i, e - (i - start))
            if jumps > -1:
                ans = min(ans, 1 + jumps )

        ans = -1 if ans == sys.maxsize else ans
        memo[start][energy] = ans
        return ans
    
    res = f(0, 0)
    # print(memo)
    return res
    
print(zbig(A))