IND VS NZ: Virat's Boundaries

[lolxxx]

For the above question I have the python solution, but it fails in hidden test cases. (Although the code pass the non hidden test cases)
Following is my code.

def findMinimumDifficulty(n: int, k: int, a: List[int]) -> int:
    # write your code here
    if n==k:
        return 0
    memo = {}  
    def backtrack(i, remaining_k, accumulated_sum, consecutive_count):
        if (i, remaining_k, accumulated_sum, consecutive_count) in memo:
            return memo[(i, remaining_k, accumulated_sum, consecutive_count)]
        if remaining_k == 0:
            return accumulated_sum
        
        elif i >= n:
            return 999999
        
        current_diff = backtrack(i + 1, remaining_k - 1, accumulated_sum + a[i] + consecutive_count, consecutive_count)
        next_diff = backtrack(i + 1, remaining_k, accumulated_sum, consecutive_count + 1)
        
        memo[(i, remaining_k, accumulated_sum, consecutive_count)] = min(current_diff, next_diff)
        return memo[(i, remaining_k, accumulated_sum, consecutive_count)]
    
    return backtrack(0, n - k, 0, 0)

Error: Time Limit Exceed.

I am also open for suggestion and new approach.
If anyone can solve it with dynamic programming, it will be very helpful.

 

[WhiteCube]

There are 2^N possible cases, but not all cases need to be calculated.

case (sum,passes)

case (x,y) produces 1 or 2 new cases
pass: (x,y+1) [if y<K]
hit: (x+y+A(i),y)

consider (10,3) and (15,3)

(15,3) can be ignored, the minimum produced after (10,3) will be lower than the minimum produced after (15,3)

N iterations, only one case for each possible y needs to be held.

2 initial cases

(A(0),0)
(0,1)

 

[WhiteCube]

P(0)=A(0)
P(1)=0
LAST=1
FOR I=1 TO N-1
  Q=P:'copy previous it
  FOR J=0 TO LAST
    P(J)=Q(J)+J+A(I):'hits
  IF LAST<K THEN LAST+=1
  FOR J=1 TO LAST
    IF Q(J-1)<P(J) THEN
      P(J)=Q(J-1):'passes

minimum = P(K)

 

[lolxxx]

P(0)=A(0)
P(1)=0
LAST=1
FOR I=1 TO N-1
  Q=P:'copy previous it
  FOR J=0 TO LAST
    P(J)=Q(J)+J+A(I):'hits
  IF LAST<K THEN LAST+=1
  FOR J=1 TO LAST
    IF Q(J-1)<P(J) THEN
      P(J)=Q(J-1):'passes

minimum = P(K)

Thank you so much ^^