Min cost path (Memoization)

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

This algorithm uses memoization to improve performance. It's same as the recursive version of Min cost path, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = None

def move(c, i, j):
  if i < 0 or j < 0:
    return float('inf')
  
  global cache
  if not cache:
    cache = [[None] * len(c[0]) for _ in range(len(c))]

  if not cache[i][j]:
    if i == 0 and j == 0:
      cache[i][j] = c[0][0]
    else:
      cache[i][j] = c[i][j] + min(move(c, i - 1, j), move(c, i, j - 1), move(c, i - 1, j - 1))

  return cache[i][j] 

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

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

let cache = null;

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

  if (!cache) {
    cache = Array.from(Array(c.length), () => Array(c[0].lenth));
  }

  if (!cache[i][j]) {
    if (i === 0 && j === 0) {
      cache[i][j] = c[0][0];
    } else {
      cache[i][j] = c[i][j] + Math.min(move(c, i - 1, j), move(c, i, j - 1), move(c, i - 1, j - 1));
    }
  }

  return cache[i][j];
}

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

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