64 Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Example:

1 3 1
1 5 1 -> return 7
4 2 1

Note: You can only move either down or right at any point in time.

The Idea: This problem reminded me of seam carving in computer vision. This problem follows a familiar design, and the proof (via induction) as to why it works is the same. Suppose we have the following matrix

1  5  1 
2  1  3
8  7 10

Begin by accumulating the top row and left column. We do this because it this sort of logic is unique to only these areas of the matrix. Performing this separately simplifies the logic later. What distinguishes these elements is that they can only accumulate from one direction respectively (towards the right, and down). Every other matrix element has one of two options.

 1  6  7
 3  1  3
11  9 10

Next, we work on the bottom right sub matrix (matrix[1:end][1:end]). These areas have two options (to take a path from either the bottom or top. To understand why this works, we can see how this works for the base case (first row), and then inductively prove how every next row can independently be treated exactly the same as the base case.

 1  6  7
 3  4  7
11 13 17

It then follows that the bottom right matrix element is the minimum accumulative sum. If we'd like we can backtrack to actually find this path. Simply take the minimum left or top matrix element beginning from the bottom right matrix element until the starting matrix element is reached.

Complexity: O(n) time, and O(n) extra space

void init_perimeter(vector<vector<int>> &grid) {
    const size_t rows = grid.size(), cols = grid.at(0).size();
    int prev_sum;

    prev_sum = 0; // top
    for (int i = 0; i < cols; i++) {
        grid[0][i] += prev_sum;
        prev_sum = grid[0][i];
    }

    prev_sum = 0; // left
    for (int i = 0; i < rows; i++) {
        grid[i][0] += prev_sum;
        prev_sum = grid[i][0];
    }
}

void dp_min_diag(vector<vector<int>> &grid) {
    for (int i = 0; i < grid.size() - 1; i++) {
        for (int j = 0; j < grid.at(i).size() - 1; j++) {
            int bottom = grid[i + 1][j], right = grid[i][j + 1];
            grid[i + 1][j + 1] += min(bottom, right);
        }
    }
}

int minPathSum(vector<vector<int>>& grid) {
    if (grid.empty()) return 0;

    const size_t rows = grid.size(), cols = grid.at(0).size();
    init_perimeter(grid);
    dp_min_diag(grid);

    return grid[rows - 1][cols - 1];
}