1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int minFallingPathSum(vector<vector<int>>& a) {
int n = a.size();
int m = a[0].size();
int dp[n][m];
int ans = 1e9;
memset(dp, 0, sizeof dp);
for (int i = 0;i<n;i++) {
for(int j = 0; j<m; j++) {
if (i!=0) {
dp[i][j] = dp[i-1][j];
if (j > 0) dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
if (j + 1 < m) dp[i][j] = min(dp[i][j], dp[i-1][j+1]);
}
dp[i][j] += a[i][j];
if (i==n-1) {
ans = min(ans, dp[i][j]);
}
}
}
return ans;
}
};
|