commit 94e31f04c637a106ab7a12a58de8a7394f1c631d
parent 1d2c19f97d65f87b641e11127c0853f6e3fb5b7c
Author: Jack Sangdahl <jack@pngu.org>
Date: Tue, 27 Jan 2026 20:41:11 -0700
3651. minimum cost path with teleportation
Diffstat:
2 files changed, 151 insertions(+), 0 deletions(-)
diff --git a/min_cost_path_teleportation.c b/min_cost_path_teleportation.c
@@ -0,0 +1,94 @@
+// 3651. Minimum Cost Path with Teleportations
+#include "leetcode.h"
+
+/*
+ * you are given an '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 righ or down from your current cell '(i, j)' ie. 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)'.
+ */
+
+int minCost(int **grid, int gridSize, int *gridColSize, int k) {
+ int m = gridSize, n = gridColSize[0];
+ int total = (k + 1) * m * n;
+ int *dp = (int *)malloc(total * sizeof(int));
+ int *min_cost = (int *)malloc(10002 * sizeof(int));
+ for (int i = 0; i < total; i++)
+ dp[i] = INT_MAX;
+ dp[0] = 0;
+ for (int t = 0; t <= k; t++) {
+ int offset = t * m * n;
+ for (int r = 0; r < m; r++) {
+ for (int c = 0; c < n; c++) {
+ int curr = offset + r * n + c;
+ if (dp[curr] == INT_MAX)
+ continue;
+ int cost = dp[curr];
+ if (r + 1 < m) {
+ int down = offset + (r + 1) * n + c;
+ long long next = (long long)cost + grid[r + 1][c];
+ dp[down] = fmin(dp[down], next);
+ }
+ if (c + 1 < n) {
+ int right = offset + r * n + (c + 1);
+ long long next = (long long)cost + grid[r][c + 1];
+ dp[right] = fmin(dp[right], next);
+ }
+ }
+ }
+ if (t < k) {
+ for (int i = 0; i < 10002; i++)
+ min_cost[i] = INT_MAX;
+ for (int r = 0; r < m; r++) {
+ for (int c = 0; c < n; c++) {
+ int idx = offset + r * n + c;
+ if (dp[idx] != INT_MAX) {
+ int val = grid[r][c];
+ min_cost[val] = fmin(min_cost[val], dp[idx]);
+ }
+ }
+ }
+ int curr_min = INT_MAX;
+ for (int v = 10000; v >= 0; v--) {
+ if (min_cost[v] < curr_min)
+ curr_min = min_cost[v];
+ else
+ min_cost[v] = curr_min;
+ }
+ int next = (t + 1) * m * n;
+ for (int r = 0; r < m; r++) {
+ for (int c = 0; c < n; c++) {
+ int val = grid[r][c];
+ int idx = next + r * n + c;
+ dp[idx] = fmin(dp[idx], min_cost[val]);
+ }
+ }
+ }
+ }
+ int ans = INT_MAX, idx = (m - 1) * n + (n - 1);
+ for (int t = 0; t <= k; t++) {
+ int i = t * m * n + idx;
+ ans = fmin(ans, dp[idx]);
+ }
+ free(dp);
+ free(min_cost);
+ return ans;
+}
+
+int main() {
+ int g1i[3][3] = {{1, 3, 3}, {2, 5, 4}, {4, 3, 5}};
+ int g2i[3][2] = {{1, 2}, {2, 3}, {3, 4}};
+ struct two_d_arr *g1 =
+ two_d_arr_init(ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+ struct two_d_arr *g2 =
+ two_d_arr_init(ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+ printf("%d\n", minCost(g1->arr, g1->row_size, g1->col_size, 2)); // expect: 7
+ printf("%d\n", minCost(g2->arr, g2->row_size, g2->col_size, 1)); // expect: 9
+ two_d_arr_free(g1);
+ two_d_arr_free(g2);
+}
diff --git a/min_cost_path_teleportation.py b/min_cost_path_teleportation.py
@@ -0,0 +1,57 @@
+# 3651. Minimum Cost Path with Teleportations
+from itertools import accumulate
+
+"""
+you are given an '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 righ or down from your current cell '(i, j)' ie. 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 ttotals 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)'.
+"""
+
+
+class Solution(object):
+ def minCost(self, grid, k):
+ """
+ :type grid: List[List[int]]
+ :type k: int
+ :rtype: int
+ """
+ m, n = len(grid), len(grid[0])
+ total = max([max(row) for row in grid])
+ dp = None
+ costs = [[0] * n for _ in range(m)]
+ for x in range(k + 1):
+ for i in range(m - 1, -1, -1):
+ for j in range(n - 1, -1, -1):
+ costs[i][j] = float("inf")
+ if i == m - 1 and j == n - 1:
+ costs[i][j] = 0
+ else:
+ if i < m - 1:
+ s = costs[i + 1][j] + grid[i + 1][j]
+ if s < costs[i][j]:
+ costs[i][j] = s
+ if j < n - 1:
+ s = costs[i][j + 1] + grid[i][j + 1]
+ if s < costs[i][j]:
+ costs[i][j] = s
+ if x > 0 and dp[grid[i][j]] < costs[i][j]:
+ costs[i][j] = dp[grid[i][j]]
+ dp = [float("inf")] * (total + 1)
+ for i in range(m):
+ for j in range(n):
+ if costs[i][j] < dp[grid[i][j]]:
+ dp[grid[i][j]] = costs[i][j]
+ dp = list(accumulate(dp, min))
+ return costs[0][0]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minCost(grid=[[1, 3, 3], [2, 5, 4], [4, 3, 5]], k=2))
+ print(obj.minCost(grid=[[1, 2], [2, 3], [3, 4]], k=1))
