C/C++ Coding Exercise – Minimum Path Sum – Online Judge – Dynamic Programming – LeetCode

This is one of the classic DP (Dynamic Programming) exercises that you might be asked during your interview. To submit your solutions, you can visit LeetCode Online Judge.

The question asks for minimal path sum from left-top to right-bottom for a m X n grid (so it is a rectangle array or matrix).

The path starts from top-left corner and can have only two directions, right or down.

The DP relation is:

For all x > 0 and y > 0

For first column or row, it is similar:

and for all x > 0 and y > 0

DP works because the final solution can be divided into two sub-problems, i.e. its sum on its previous two directions, up and left. If the sub-problems are not the optimal solution, you can always find a less path sum by replacing the solutions for its sub-problems.

The following C/C++ code computes the minimal sum in place (no additional storage) and the overall complexity is .

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 minPathSum(vector<vector > &grid) {
        /* get grid size */
        int r = grid.size();
        int w = grid[0].size();
        /* filling the first row */
        for (int i = 1; i < w; i ++) {
            grid[0][i] += grid[0][i - 1];
        }
        /* filling the first column */
        for (int j = 1; j < r; j ++) {
            grid[j][0] += grid[j - 1][0];
        }
        /* DP */
        for (int i = 1; i < r; i ++) {
            for (int j = 1; j < w; j ++) {
                grid[i][j] += ((grid[i - 1][j] < grid[i][j - 1]) ? grid[i - 1][j] : grid[i][j - 1]);
            }
        }
        /* return the last element */
        return grid[r - 1][w - 1];
    }
};

class Solution {
public:
    int minPathSum(vector<vector > &grid) {
        /* get grid size */
        int r = grid.size();
        int w = grid[0].size();
        /* filling the first row */
        for (int i = 1; i < w; i ++) {
            grid[0][i] += grid[0][i - 1];
        }
        /* filling the first column */
        for (int j = 1; j < r; j ++) {
            grid[j][0] += grid[j - 1][0];
        }
        /* DP */
        for (int i = 1; i < r; i ++) {
            for (int j = 1; j < w; j ++) {
                grid[i][j] += ((grid[i - 1][j] < grid[i][j - 1]) ? grid[i - 1][j] : grid[i][j - 1]);
            }
        }
        /* return the last element */
        return grid[r - 1][w - 1];
    }
};

–EOF (The Ultimate Computing & Technology Blog) —