diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /min_falling_path_sum.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'min_falling_path_sum.c')
-rw-r--r-- | min_falling_path_sum.c | 37 |
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; +} |