Minimum Path Sum Solutions in C++

// Source : https://oj.leetcode.com/problems/minimum-path-sum/
// Author : Hao Chen
// Date   : 2014-06-21



#include <limits.h>
#include <iostream>
#include <vector>
using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    for (int i=0; i<grid.size(); i++) {
        for (int j=0; j<grid[0].size(); j++) {
            if (i==0 && j==0) continue;
            else if (i==0) grid[0][j] += grid[0][j-1];
            else if (j==0) grid[i][0] += grid[i-1][j];
            else grid[i][j] += min( grid[i-1][j], grid[i][j-1]);
        }
    }
    return grid[grid.size()-1][grid[0].size()-1];
}

int main()
{
    int a[6][2]={{7,2},{6,6},{8,6},{8,7},{5,0},{6,0}};
    vector< vector<int> > grid;
    for(int i=0; i<6; i++){
        vector<int> v;
        for(int j=0; j<2; j++){
            v.push_back(a[i][j]);
        }
        grid.push_back(v);
    }

    cout << "minPathSum=" << minPathSum(grid) << endl;

    return 0;
}

#include <algorithm>
#include <vector>

using std::vector;

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        for (decltype(grid.size()) i=0; i<grid.size(); ++i)
            for (decltype(grid[0].size()) j=0; j<grid[0].size(); ++j)
                if (i == 0 && j == 0) continue;
                else if (i == 0) grid[i][j] += grid[i][j-1];
                else if (j == 0) grid[i][j] += grid[i-1][j];
                else grid[i][j] += std::min(grid[i-1][j], grid[i][j-1]);
        return grid.back().back();
    }
};

/// Source : https://leetcode.com/problems/minimum-path-sum/description/
/// Author : liuyubobobo
/// Time   : 2017-11-21

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Dynamic Programming
/// with O(n^2) space
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {

        int n = grid.size();
        assert(n > 0);

        int m = grid[0].size();
        assert(m > 0);

        vector<vector<int>> res = grid;

        for(int j = 1 ; j < m ; j ++)
            res[0][j] += res[0][j-1];

        for(int i = 1 ; i < n ; i ++)
            res[i][0] += res[i-1][0];

        for(int i = 1 ; i < n ; i ++)
            for(int j = 1 ; j < m ; j ++)
                res[i][j] += min(res[i-1][j], res[i][j-1]);

        return res[n-1][m-1];
    }
};

int main() {

    vector<vector<int>> grid = {{1, 3, 1},
                                {1, 5, 1},
                                {4, 2, 1}};
    cout << Solution().minPathSum(grid) << endl;
    return 0;
}

/// Source : https://leetcode.com/problems/minimum-path-sum/description/
/// Author : liuyubobobo
/// Time   : 2017-11-21

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Dynamic Programming
/// with O(n) space, actually 2*n space
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {

        int n = grid.size();
        assert(n > 0);

        int m = grid[0].size();
        assert(m > 0);

        vector<vector<int>> res(2, vector<int>(m, 0));
        res[0][0] = grid[0][0];

        for(int j = 1 ; j < m ; j ++)
            res[0][j] = grid[0][j] + res[0][j-1];

        for(int i = 1 ; i < n ; i ++){
            res[i%2][0] = grid[i][0] + res[(i-1)%2][0];
            for(int j = 1 ; j < m ; j ++)
                res[i%2][j] = grid[i][j] + min(res[(i-1)%2][j], res[i%2][j-1]);
        }

        return res[(n-1)%2][m-1];
    }
};

int main() {

    vector<vector<int>> grid = {{1, 3, 1},
                                {1, 5, 1},
                                {4, 2, 1}};
    cout << Solution().minPathSum(grid) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-path-sum/description/
/// Author : liuyubobobo
/// Time   : 2017-11-21

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Dynamic Programming
/// with O(n) space, just n space.
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {

        int n = grid.size();
        assert(n > 0);

        int m = grid[0].size();
        assert(m > 0);

        vector<int> res(m, 0);
        res[0] = grid[0][0];

        for(int j = 1 ; j < m ; j ++)
            res[j] = grid[0][j] + res[j-1];

        for(int i = 1 ; i < n ; i ++){
            res[0] += grid[i][0];
            for(int j = 1 ; j < m ; j ++)
                res[j] = grid[i][j] + min(res[j], res[j-1]);
        }

        return res[m-1];
    }
};

int main() {

    vector<vector<int>> grid = {{1, 3, 1},
                                {1, 5, 1},
                                {4, 2, 1}};
    cout << Solution().minPathSum(grid) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-path-sum/description/
/// Author : liuyubobobo
/// Time   : 2017-11-21

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Dynamic Programming
/// with O(1) space, get the answer based on the original space
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(1)
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {

        int n = grid.size();
        assert(n > 0);

        int m = grid[0].size();
        assert(m > 0);

        for(int j = 1 ; j < m ; j ++)
            grid[0][j] += grid[0][j-1];

        for(int i = 1 ; i < n ; i ++)
            grid[i][0] += grid[i-1][0];

        for(int i = 1 ; i < n ; i ++)
            for(int j = 1 ; j < m ; j ++)
                grid[i][j] += min(grid[i-1][j], grid[i][j-1]);

        return grid[n-1][m-1];
    }
};

int main() {

    vector<vector<int>> grid = {{1, 3, 1},
                                {1, 5, 1},
                                {4, 2, 1}};
    cout << Solution().minPathSum(grid) << endl;
    return 0;
}