aboutsummaryrefslogtreecommitdiff
path: root/min_falling_path_sum2.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /min_falling_path_sum2.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'min_falling_path_sum2.c')
-rw-r--r--min_falling_path_sum2.c42
1 files changed, 42 insertions, 0 deletions
diff --git a/min_falling_path_sum2.c b/min_falling_path_sum2.c
new file mode 100644
index 0000000..128fb85
--- /dev/null
+++ b/min_falling_path_sum2.c
@@ -0,0 +1,42 @@
+// 1289. Minimum Falling Path Sum II
+#include "leetcode.h"
+
+/*
+ * given a 'n * n' integer matrix 'grid' return the minimum sum of a falling
+ * path with non zero shifts. a falling path with non zero shifts is a choice of
+ * exactly one element from each row of 'grid' such that no two elements chosen
+ * in adjacent rows are in the same column
+ */
+
+int min(int **grid, int gridSize, int *gridColSize, int curr) {
+ int min = INT_MAX;
+ for (int i = 0; i < curr; i++)
+ if (min > grid[gridSize][i])
+ min = grid[gridSize][i];
+ for (int i = curr + 1; i < *gridColSize; i++)
+ if (min > grid[gridSize][i])
+ min = grid[gridSize][i];
+ return min;
+}
+
+int minFallingPathSum(int **grid, int gridSize, int *gridColSize) {
+ int **list = (int **)malloc(sizeof(int *) * 2);
+ list[0] = malloc(sizeof(int) * *gridColSize);
+ list[1] = malloc(sizeof(int) * *gridColSize);
+ gridSize--;
+ int k = gridSize % 2;
+ for (int i = 0; i < *gridColSize; i++)
+ list[k][i] = grid[gridSize][i];
+ gridSize--;
+ int other = k;
+ while (gridSize >= 0) {
+ k = gridSize % 2;
+ for (int i = 0; i < *gridColSize; i++)
+ list[k][i] = min(list, other, gridColSize, i) + grid[gridSize][i];
+ other = k;
+ gridSize--;
+ }
+ int ans = min(list, 0, gridColSize, *gridColSize);
+ free(list[0]), free(list[1]), free(list);
+ return ans;
+}