leetcode

commit 3e752654e7d84fcec7519f719088757f74c0ded4
parent 738535d11be07f7840c63e3b822995e2062dd565
Author: Jack Sangdahl <jack@pngu.org>
Date:   Wed,  1 Apr 2026 20:56:01 -0600

3418. maximum amount of money robot can earn

Diffstat:
A
max_amount_money_robot_earn.c
 | 
67
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
max_amount_money_robot_earn.py
 | 
51
+++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 118 insertions(+), 0 deletions(-)
diff --git a/max_amount_money_robot_earn.c b/max_amount_money_robot_earn.c
@@ -0,0 +1,67 @@
+// 3418. Maximum Amount of Money Robot Can Earn
+#include "leetcode.h"
+
+/*
+ * you are given an 'm x n' grid. a robot starts at the top left corner of the
+ * grid '(0, 0)' and wants to reach the bottom right corner '(m - 1, n - 1)'.
+ * the robot can either move right or down at any point in time. the grid
+ * contains a value 'coins[i][j]' in each cell the robot has a special ability
+ * to neutralise in at most 2 cells on its path, prevening them from stealing
+ * coins in those cells. return the maximum profit the robot can gain on the
+ * route.
+ */
+
+int dfs(int **coins, int ***memo, int m, int n, int i, int j, int k) {
+  if (i < 0 || j < 0)
+    return INT_MIN;
+  int x = coins[i][j];
+  if (!i && !j)
+    return k > 0 ? (x > 0 ? x : 0) : x;
+  if (memo[i][j][k] != INT_MIN)
+    return memo[i][j][k];
+  int res = fmax(dfs(coins, memo, m, n, i - 1, j, k),
+                 dfs(coins, memo, m, n, i, j - 1, k)) +
+            x;
+  if (k > 0 && x < 0)
+    res = fmax(res, fmax(dfs(coins, memo, m, n, i - 1, j, k - 1),
+                         dfs(coins, memo, m, n, i, j - 1, k - 1)));
+  memo[i][j][k] = res;
+  return res;
+}
+int maximumAmount(int **coins, int coinsSize, int *coinsColSize) {
+  int m = coinsSize, n = coinsColSize[0];
+  int ***memo = (int ***)malloc(m * sizeof(int **));
+  for (int i = 0; i < m; i++) {
+    memo[i] = (int **)malloc(n * sizeof(int *));
+    for (int j = 0; j < n; j++) {
+      memo[i][j] = (int *)malloc(3 * sizeof(int));
+      for (int k = 0; k < 3; k++)
+        memo[i][j][k] = INT_MIN;
+    }
+  }
+  int res = dfs(coins, memo, m, n, m - 1, n - 1, 2);
+  for (int i = 0; i < m; i++) {
+    for (int j = 0; j < n; j++)
+      free(memo[i][j]);
+    free(memo[i]);
+  }
+  free(memo);
+  return res;
+}
+
+int main() {
+  int c1i[3][3] = {{0, 1, -1}, {1, -2, 3}, {2, -3, 4}};
+  int c2i[2][3] = {{10, 10, 10}, {10, 10, 10}};
+  struct two_d_arr *c1 =
+      two_d_arr_init(ARRAY_SIZE(c1i), ARRAY_SIZE(c1i[0]), c1i);
+  struct two_d_arr *c2 =
+      two_d_arr_init(ARRAY_SIZE(c2i), ARRAY_SIZE(c1i[0]), c2i);
+  int r1 = maximumAmount(c1->arr, c1->row_size, c1->col_size);
+  int r2 = maximumAmount(c2->arr, c2->row_size, c2->col_size);
+  printf("%d\n", r1);
+  assert(r1 == 8);
+  printf("%d\n", r2);
+  assert(r2 == 40);
+  two_d_arr_free(c1);
+  two_d_arr_free(c2);
+}
diff --git a/max_amount_money_robot_earn.py b/max_amount_money_robot_earn.py
@@ -0,0 +1,51 @@
+# 3418. Maximum Amount of Money Robot Can Earn
+from typing import List
+
+"""
+you are given an 'm x n' grid. a robot starts at the top left corner of the
+grid '(0, 0)' and wants to reach the bottom right corner '(m - 1, n - 1)'.
+the robot can either move right or down at any point in time. the grid
+contains a value 'coins[i][j]' in each cell the robot has a special ability
+to neutralise in at most 2 cells on its path, prevening them from stealing
+coins in those cells. return the maximum profit the robot can gain on the
+route.
+"""
+
+
+class Solution:
+    def maximumAmount(self, coins: List[List[int]]) -> int:
+        m, n = len(coins), len(coins[0])
+        dp = [[[float("-inf")] * 3 for _ in range(n)] for _ in range(m)]
+        dp[0][0][0] = coins[0][0]
+        for k in range(1, 3):
+            dp[0][0][k] = max(coins[0][0], 0)
+        for j in range(1, n):
+            for k in range(3):
+                dp[0][j][k] = dp[0][j - 1][k] + coins[0][j]
+                if k > 0:
+                    dp[0][j][k] = max(
+                        dp[0][j][k], dp[0][j - 1][k - 1] + max(coins[0][j], 0)
+                    )
+        for i in range(1, m):
+            for k in range(3):
+                dp[i][0][k] = dp[i - 1][0][k] + coins[i][0]
+                if k > 0:
+                    dp[i][0][k] = max(
+                        dp[i][0][k], dp[i - 1][0][k - 1] + max(coins[i][0], 0)
+                    )
+        for i in range(1, m):
+            for j in range(1, n):
+                for k in range(3):
+                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k]) + coins[i][j]
+                    if k > 0:
+                        dp[i][j][k] = max(
+                            dp[i][j][k],
+                            max(dp[i - 1][j][k - 1], dp[i][j - 1][k - 1]),
+                        )
+        return dp[m - 1][n - 1][2]
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.maximumAmount(coins=[[0, 1, -1], [1, -2, 3], [2, -3, 4]]))
+    print(obj.maximumAmount(coins=[[10, 10, 10], [10, 10, 10]]))