Given a 2d matrix cost[][], calculate the minimum cost path from (0, 0) to (m, n). Only move down, right and diagonally lower cells from a given cell is allowed.

Hint

Recursive Approach: The algorithm defines a relationship between the cost at the current position (target) and the cost at the positions preceding it. This means the cost at the current position is calculated based on the minimum cost among three possible moves from the previous positions: moving up, moving left and moving diagonally up-left.

# Python implementation

def move(c, i, j):
  if i < 0 or j < 0:
    return float('inf')

  if i == 0 and j == 0:
    return c[0][0]

  return c[i][j] + min(move(c, i - 1, j), move(c, i, j - 1), move(c, i - 1, j - 1))

cost = [
  [1, 2, 3],
  [4, 8, 2],
  [1, 5, 3]
]
target = [2, 2]

print(move(cost, target[0], target[1]))

// Javascript implementation

function move(c, i, j) {
  if (i < 0 || j < 0) {
    return Infinity;
  }

  if (i === 0 && j === 0) {
    return c[0][0];
  }

  return c[i][j] + Math.min(move(c, i - 1, j), move(c, i, j - 1), move(c, i - 1, j - 1));
}

const cost = [
  [1, 2, 3],
  [4, 8, 2],
  [1, 5, 3]
];
const target = [2, 2];

console.log(move(cost, target[0], target[1]));

Min cost path

Hint