aboutsummaryrefslogtreecommitdiff
path: root/min_falling_path_sum.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_sum.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'min_falling_path_sum.c')
-rw-r--r--min_falling_path_sum.c37
1 files changed, 37 insertions, 0 deletions
diff --git a/min_falling_path_sum.c b/min_falling_path_sum.c
new file mode 100644
index 0000000..77cfee1
--- /dev/null
+++ b/min_falling_path_sum.c
@@ -0,0 +1,37 @@
+// 931. Minimum Falling Path Sum
+#include "leetcode.h"
+
+/*
+ * given an 'n * n' array of integers 'matrix', return the minimum sum of any
+ * falling path through 'matrix'. a falling path starts at any element in the
+ * first row and choose the element in the next row that is either directly
+ * below or diagonally left/right. specifically, the next element from position
+ * '(row, col)' will be '(row + 1, col - 1), (row + 1, col), or (row + 1, col +
+ * 1)'.
+ */
+
+int minFallingPathSum(int **matrix, int matrix_size, int *matrix_col_size) {
+ int **dp = (int **)malloc(sizeof(int *) * matrix_size);
+ for (int i = 0; i < matrix_size; i++) {
+ int *tmp = (int *)malloc(sizeof(int) * matrix_col_size[i]);
+ memset(tmp, 0, matrix_col_size[i]);
+ dp[i] = tmp;
+ }
+ for (int i = 0, n = matrix_col_size[0]; i < n; i++)
+ dp[0][i] = matrix[0][i];
+ for (int i = 1; i < matrix_size; i++) {
+ for (int j = 0, n = matrix_col_size[i]; j < n; j++) {
+ if (!j)
+ dp[i][j] = matrix[i][j] + fmin(dp[i - 1][j], dp[i - 1][j + 1]);
+ else if (j == n - 1)
+ dp[i][j] = matrix[i][j] + fmin(dp[i - 1][j], dp[i - 1][j - 1]);
+ else
+ dp[i][j] = matrix[i][j] +
+ fmin(dp[i - 1][j - 1], fmin(dp[i - 1][j], dp[i - 1][j + 1]));
+ }
+ }
+ int ans = INT_MAX;
+ for (int i = 0, n = matrix_col_size[matrix_size - 1]; i < n; i++)
+ ans = fmin(ans, dp[matrix_size - 1][i]);
+ return ans;
+}