3651. Minimum Cost Path with Teleportations

Description

You are given a m x n 2D integer array grid and an integer k. You start at the top-left cell (0, 0) and your goal is to reach the bottom‐right cell (m - 1, n - 1).

There are two types of moves available:

• Normal move: You can move right or down from your current cell (i, j), i.e. you can move to (i, j + 1) (right) or (i + 1, j) (down). The cost is the value of the destination cell.

• Teleportation: You can teleport from any cell (i, j), to any cell (x, y) such that grid[x][y] <= grid[i][j]; the cost of this move is 0. You may teleport at most k times.

Return the minimum total cost to reach cell (m - 1, n - 1) from (0, 0).

 

Example 1:

Input: grid = [[1,3,3],[2,5,4],[4,3,5]], k = 2

Output: 7

Explanation:

Initially we are at (0, 0) and cost is 0.

Current Position	Move	New Position	Total Cost
(0, 0)	Move Down	(1, 0)	0 + 2 = 2
(1, 0)	Move Right	(1, 1)	2 + 5 = 7
(1, 1)	Teleport to (2, 2)	(2, 2)	7 + 0 = 7

The minimum cost to reach bottom-right cell is 7.

Example 2:

Input: grid = [[1,2],[2,3],[3,4]], k = 1

Output: 9

Explanation:

Initially we are at (0, 0) and cost is 0.

Current Position	Move	New Position	Total Cost
(0, 0)	Move Down	(1, 0)	0 + 2 = 2
(1, 0)	Move Right	(1, 1)	2 + 3 = 5
(1, 1)	Move Down	(2, 1)	5 + 4 = 9

The minimum cost to reach bottom-right cell is 9.

 

Constraints:

• 2 <= m, n <= 80
• m == grid.length
• n == grid[i].length
• 0 <= grid[i][j] <= 104
• 0 <= k <= 10

 

Solutions

Solution: Dynamic Programming

• Time complexity: O((k+logmn)*mn)
• Space complexity: O(mn)

 

JavaScript

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
const minCost = function (grid, k) {
  const m = grid.length;
  const n = grid[0].length;
  const points = [];

  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      points.push({ row, col, value: grid[row][col] });
    }
  }

  points.sort((a, b) => a.value - b.value);

  const costs = Array.from({ length: m }, () => {
    return new Array(n).fill(Number.MAX_SAFE_INTEGER);
  });

  for (let t = 0; t <= k; t++) {
    let minCost = Number.MAX_SAFE_INTEGER;
    let left = 0;

    for (let index = 0; index < points.length; index++) {
      const { row, col, value } = points[index];
      const next = points[index + 1];

      minCost = Math.min(minCost, costs[row][col]);

      if (index + 1 < points.length && value === next.value) {
        continue;
      }

      for (let r = left; r <= index; r++) {
        costs[points[r].row][points[r].col] = minCost;
      }

      left = index + 1;
    }

    for (let row = m - 1; row >= 0; row--) {
      for (let col = n - 1; col >= 0; col--) {
        if (row === m - 1 && col === n - 1) {
          costs[row][col] = 0;
          continue;
        }

        if (row !== m - 1) {
          const cost = costs[row + 1][col] + grid[row + 1][col];

          costs[row][col] = Math.min(costs[row][col], cost);
        }

        if (col !== n - 1) {
          const cost = costs[row][col + 1] + grid[row][col + 1];

          costs[row][col] = Math.min(costs[row][col], cost);
        }
      }
    }
  }

  return costs[0][0];
};