leetcode

0 class Solution {

1 int n;

2

3 bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }

4

5 public:

6 int minFallingPathSum(vector<vector<int>> &matrix) {

7 n = matrix.size();

8

9 for (int i = n - 2; i >= 0; i--) {

10 for (int j = 0; j < n; j++) {

11 int mini = INT_MAX;

12 for (int k = -1; k <= 1; k++) {

13 int x = i + 1;

14 int y = j + k;

15 if (!valid(x, y)) continue;

16 mini = min(mini, matrix[x][y]);

17 }

18 matrix[i][j] += mini;

19 }

20 }

21

22 int mini = INT_MAX;

23 for (int i = 0; i < n; i++)

24 mini = min(mini, matrix[0][i]);

25 return mini;

26 }

27 };