leetcode

// 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;
}