Choose exactly one entry from each row of the square grid. Entries chosen in consecutive rows must be in different columns; the column may change by any nonzero distance. Return the smallest possible sum of the chosen entries.
Hatched cells show one minimum-sum path with different columns in adjacent rows.
Example 1:
Input: grid = [[1,9],[2,8]]
Output: 9Explanation: There are two valid choices: 1 followed by 8, or 9 followed by 2. The smaller sum is 9. Choosing 1 then 2 is forbidden because both occupy column 0.
Example 2:
Input: grid = [[0,9,-2],[9,-3,9],[-4,9,9]]
Output: -9Explanation: Choose -2 in column 2, then -3 in column 1, then -4 in column 0. Their sum is -9. Every adjacent pair uses different columns.
Example 3:
Input: grid = [[5]]
Output: 5Explanation: With one row, choose its only entry. There is no next row imposing a column restriction, so the result is 5.
Constraints:
1 <= grid.length <= 200- Every row has
grid.lengthentries. -99 <= grid[i][j] <= 99