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_sum2.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'min_falling_path_sum2.c')
-rw-r--r-- | min_falling_path_sum2.c | 42 |
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; +} |