Min cost path in grid using jumps or unit steps right or down-CodePudding

Assume you have a grid, where each node contains a weight that represents the cost of taking that square.

You start at (0,0) at the top left of the 2D array and you want to get to (X-1, Y-1) where X is the number of columns and Y rows at the bottom right. You can go right 1 square, or you can go down 1 square at a time. You are also given an int array of "jumps", where each value $d_i$ represents the number of squares you can skip over going right or down on the ith jump. The jumps array specifies the order you have to take for jumps, meaning, for instance, you can't take jump[2] of a skip if you haven't used a single one. You can only take len(jump) number of jumps.

We are trying to solve this with dynamic programming. This is what I have thus far:

def helper(grid, jumps):
    dCount = 0
    dp = [[[0 for k in range(len(jumps) 1)] for j in  range(len(grid[0]))] for i in range(len(grid))]

    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if row == 0 and col == 0:
                dp[row][col][dCount]  = grid[row][col]
            jumpRight = float('infinity')
            jumpUp = float('infinity')
            goUp = float('infinity')
            goRight = float('infinity')
            if(row > 0):
                goUp = dp[row-1][col][dCount]
            if(col > 0):
                goRight = dp[row][col-1][dCount]
            if (dCount < len(jumps)):
                jumpRight = dp[row-jumps[dCount]][col][dCount] 
                jumpUp = dp[row][col-jumps[dCount]][dCount]
            res = grid[row][col]   min(goRight, goUp, jumpRight, jumpUp)
            if(res == jumpRight or res==jumpUp): 
                dCount =1
            dp[row][col][dCount] = res
    return dp[len(grid)-1][len(grid[0])-1]

grid = [[1, 0, 3, 7, 2, 5], [8, 3, 7, 6, 9, 8], [9, 7, 8, 2, 1, 1], [3, 2, 9, 1, 7, 8]]

jumps = [1, 1]
print(helper(grid,jumps)) #should be 16

However, the code doesn't seem to be working.

The above is just printing out [0 0 15], when I think it should be [0 0 16]

CodePudding user response：

The following is an implementation:

def shortest(grid, jumps, x=0, y=0, jumped=0):
    # grid: whole grid
    # jumps: jumps to be exhuasted
    # x, y: current position
    # jumped: number of jumps that have been used
    # output: a tuple (cost, path)
    #         cost: minimum cost from this position to the final position
    #         path: a list of tuples, each element the position along the minimum-cost path
    rows = len(grid) - x; cols = len(grid[0]) - y # remaining num of rows and cols
    if (rows, cols) == (1, 1): # if arrived at the southeast corner
        return (float('inf'), [(x, y)]) if jumps[jumped:] else (grid[x][y], [(x, y)]) # return inf if jumps are not exhausted
    candidates = [] # store results from deeper calls
    if rows > 1: # if possible to move down
        candidates.append(shortest(grid, jumps, x 1, y, jumped)) # down by one
        if jumped < len(jumps) and rows > jumps[jumped]   1: # if possible to jump
            candidates.append(shortest(grid, jumps, x jumps[jumped] 1, y, jumped 1)) # jump down
    if cols > 1: # if possible to move right
        candidates.append(shortest(grid, jumps, x, y 1, jumped)) # right by one
        if jumped < len(jumps) and cols > jumps[jumped]   1: # if possible to jump
            candidates.append(shortest(grid, jumps, x, y jumps[jumped] 1, jumped 1)) # jump right
    temp = min(candidates, key=lambda x: x[0]) # recall: temp[0]: min_cost, temp[1]: min_path
    return (temp[0]   grid[x][y], [(x, y), *temp[1]])

grid = [[1, 0, 3, 7, 2, 5], [8, 3, 7, 6, 9, 8], [9, 7, 8, 2, 1, 1], [3, 2, 9, 1, 7, 8]]

jumps = [1, 1]
print(shortest(grid, jumps)) # (16, [(0, 0), (0, 1), (0, 2), (0, 4), (2, 4), (2, 5), (3, 5)])

The state variables are x, y and jumps; x and y remember where the current position is in the given grid. jumps remembers how many jumps have been used so far.

The end state of the recursion occurs when the position is at the final destination, i.e., [-1, -1]. If the jumps have not been exhausted, then it is a failure; so return the infinity as the cost. Otherwise, return the value at the point as the cost.

Actually, the return is a tuple; the first element is the cost, and the second element is the current position. The second element is used for obtaining the cost-minimization path in the end.

In other states, the recursion is defined in a natural way; the function recurses into (up to) four possible movements: up by one, right by one, jump up, jump right. It compares the resulting costs, and selects the minimum-cost direction.

Note: this uses generalized unpack, introduced in python 3.5. But this is not essential.

CodePudding user response：

Here's an example of a bottom up approach that seems to return correct results for this example and the one in a similar question. I'm not sure the code is foolproof, though.

Python:

def f(grid, jumps):
  m, n = len(grid), len(grid[0])
  dp = [None] * m

  for i in range(m):
    dp[i] = [[float('inf')] * (len(jumps)   1) for j in range(n)]

  dp[0][0][0] = grid[0][0]

  for y in range(m):
    for x in range(n):
      for j in range(len(jumps)   1):
        if (y, x, j) == (0, 0, 0):
          continue

        dp[y][x][j] = grid[y][x]   min(
          dp[y - 1][x][j] if y > 0 else float('inf'),
          dp[y][x - 1][j] if x > 0 else float('inf'),
          dp[y - jumps[j-1] - 1][x][j-1] if (j > 0 and y - jumps[j-1] - 1 >= 0) else float('inf'),
          dp[y][x - jumps[j-1] - 1][j-1] if (j > 0 and x - jumps[j-1] - 1 >= 0) else float('inf')
        )
  
  return min(dp[m-1][n-1])


grid = [
  [1, 0, 3, 7, 2, 5],
  [8, 3, 7, 6, 9, 8],
  [9, 7, 8, 2, 1, 1],
  [3, 2, 9, 1, 7, 8]]

jumps = [1, 1]

print(f(grid, jumps)) # 16


grid = [
  [3, 9, 1],
  [9, 9, 1],
  [9, 9, 1]
]

jumps = [1, 1]

print(f(grid, jumps)) # 5