Minimum Falling Path Sum Solutions in C++

// Source : https://leetcode.com/problems/minimum-falling-path-sum/
// Author : Hao Chen
// Date   : 2019-01-30


class Solution {
private:
    int min(int x, int y) {
        return x < y ? x: y;
    }
    int min( int x, int y, int z) {
        return min(min(x, y),z);
    }
public:
    int minFallingPathSum(vector<vector<int>>& A) {
        int m = INT_MAX;
        
        for (int i=0; i<A.size(); i++) {
            for (int j=0; j<A[i].size(); j++){
                //find the minimal item in previous row, and add it into the current item
                if (i > 0) {
                    if (j == 0 ){
                       A[i][j] += min( A[i-1][j], A[i-1][j+1]); 
                    } else if ( j + 1 == A[i].size()) {
                       A[i][j] += min( A[i-1][j], A[i-1][j-1]); 
                    }else {
                        A[i][j] += min( A[i-1][j], A[i-1][j-1], A[i-1][j+1]);
                    }
                }
                
                if ( i + 1 == A.size() ) {
                    m = min(m, A[i][j]);
                }
            }
        }
        
        return m;
    }
};

/// Source : https://leetcode.com/problems/minimum-falling-path-sum/
/// Author : liuyubobobo
/// Time   : 2018-10-27

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(m * n)
/// Space Complexity: O(1)
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& A) {

        int m = A.size();
        if(m == 0) return 0;

        int n = A[0].size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));

        dp[0] = A[0];
        for(int i = 1; i < m; i ++)
            for(int j = 0; j < n; j ++)
                for(int k = max(j - 1, 0); k <= min(n - 1, j + 1); k ++)
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + A[i][j]);

        return *min_element(dp[m - 1].begin(), dp[m - 1].end());
    }
};


int main() {

    vector<vector<int>> A = {{1,2,3},{4,5,6},{7,8,9}};
    cout << Solution().minFallingPathSum(A) << endl;
    // 12

    return 0;
}