1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
|
class { public: int minFallingPathSum(vector<vector<int>>& A) { int m = A.size(); int n = A[0].size(); vector<vector<int>> dp(A);
for (int j = 0; j < n; ++j) { dp[0][j] = A[0][j]; }
for (int i = 1; i < m; ++i) { for (int j = 0; j < n; ++j) { if (j - 1 == -1) { dp[i][j] = min(dp[i-1][j], dp[i-1][j+1]) + A[i][j]; } else if (j + 1 == n) { dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + A[i][j]; } else { dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i-1][j+1]) + A[i][j]; } } }
return *min_element(dp[m-1].begin(), dp[m-1].end()); } };
|
近期评论