Find best path maximizing score in 2D array

Question

I’m trying to implement a game where the allowed moves are left to right and top to down in a N x N 2D array with random positiv floats and a null trace (0 in diagonal). The moves are not restricted to 1 cell, each move is a shift of any number of squares to the right or down.

The starting position is the top row and first column and the ending arrival point can be anywhere. There are no blocker, we can follow any path as long as the move rules (to the right or to the bottom) are respected.

The score is computed only by tacking the ending point of each move, i.e if it goes from (0,0) to (0,4), only the value of element (0,4) contributes to the score, intermediate element value involved in the move are discarted from the score. Score = sum(value of cell at move ending point)

I want to find the resulting value for the most profitable route.

I have tried the Dynamic Programming approach but it is not adapted to my problem.

# A is the 2d array
# M is the matrix of optimal scores
# n is the size of the matrix
# path is the list of positions of the optimal path

def best_path(A, n):
  # Initialization of M with the values of A
  M = [[A[i][j] for j in range(n)] for i in range(n)]
  # Filling of M usine DP
  for i in range(n):
    for j in range(n):
      if i > 0 and j > 0:
        M[i][j] = max(M[i-1][j] + A[i][j], max(M[i][k] + A[i][j] for k in range(j)))
      elif i > 0 and j == 0:
        M[i][j] = M[i-1][j] + A[i][j]
      elif i == 0 and j > 0:
        M[i][j] = max(M[i][k] + A[i][j] for k in range(j))
  # The maximum score of the optimal path is M[n-1][n-1]
  score = M[n-1][n-1]
  # Initialization of the path with the end point
  path = [(n-1, n-1)]
  # Initialization of the indices i and j with the end point
  i = n-1
  j = n-1
  # Going back to the starting point by choosing the movement that maximizes the score
  while i > 0 or j > 0:
    if i > 0 and j > 0:
      if M[i][j] == M[i-1][j] + A[i][j]:
        # Move up
        i = i - 1
      else:
        # Move left until we find the k that maximizes the score
        k = max(range(j), key=lambda k: M[i][k] + A[i][j])
        j = k
    elif i > 0 and j == 0:
        # Move up 
      i = i - 1
    elif i == 0 and j > 0:
      # Move left until we find the k that maximizes the score
      k = max(range(j), key=lambda k: M[i][k] + A[i][j])
      j = k
    # Add the current position to the path
    path.append((i, j))
  # Reverse the path to have the right order
  path.reverse()
  # Return the score and the path
  return score, path

Any help will be very appreciated