Project Euler #81: Path sum: two ways

Problem Link: here

Question:

You’re given an N * N matrix . The task is to find the minimal path sum from the top left to the bottom right, by only moving to the right and down. Let’s say we have the following N = 5 and grid[5][5]

5
131 673 234 103 18
201 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331

The minimal path is 2427 for this grid shown by bold numbers in grid

Approach:
In order to solve this problem , say we are at position (i, j). We can reach (i, j) from (i - 1, j) or (i, j - 1). Let dp[n][n] be the new grid such that dp[i][j] is the cost to reach position (i, j). So, the equation is

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];

Let’s consider the position (0, 0). Clearly, we can write

dp[0][0] = grid[0][0];

as there is no any path to reach cell (0, 0)
For all the remaining values at row 0. We can reach position (i, j) from left i.e (i, j -1) so

dp[i][j] = dp[i][j - 1] + grid[i][j];

For all the 0th column (i, 0), the only possible place to reach is from up (i - 1, 0) so

dp[i][j] = dp[i - 1][j] + grid[i][j];

Here is the implementaion of above approach in C++

//Author: Bishal Sarang
#include<bits/stdc++.h>
using namespace std;
 
//typedefs
typedef long long ll;
 
int main() {
 int n; cin >> n;
 vector grid(n, vector(n));
 vector dp(n , vector(n, 0));
 
 //Read Grid
 for(int i = 0; i < n; i++){
  for(int j = 0; j < n; j++){
    cin >> grid[i][j];
  }
 }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(i == 0 ){
 
        //Case (0, 0)
        if(j == 0){
          //There is no way to reach (0, 0). So the cost to
          //reach (0, 0) is dp[0][0] = grid[0][0]
          dp[i][j] = grid[i][j];
        }
        //Remaining values for 0th row
        else{
            //There is only 1 way to reach (i, j) for remaining values in 0th row i.e from left
            dp[i][j] = dp[i][j - 1] + grid[i][j];
        }
      }
      //Case (i, 0): first row
      else if(j == 0){
        //First column can be reached only from the cell above it
        dp[i][j] = dp[i - 1][j] + grid[i][j];
      }
      //Case(i, j): remaining positions
      else{
        // (i, j) can be reached either from left : (i, j - 1) or up (i - 1, j)
        //We choose minimum of both
        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
      }
 
  }
 }
 
 //Cost to reach the destination (n - 1, n - 1) is dp[n - 1][n - 1];
 cout << dp[n - 1][n - 1];
 return 0;
}

Complexity:

Since we have used an auxiliary array of N * N , the space complexity is O(N * N)
The time complexity is O(N * N) as we visit every cells.

Improvements:
The space complexity can be reduced to O(N) by using a 1D array just to store the value of previous rows and using it to calculate for the next row

//Author: Bishal Sarang
#include<bits/stdc++.h>
using namespace std;
 
//typedefs
typedef long long ll;
 
int main() {
 int n; cin >> n;
 vector grid(n, vector(n));
 //dp[n] stores the minimum cost for previous rows
 vector dp(n , 0);
 
 //Read Grid
  for(int i = 0; i < n; i++){
  for(int j = 0; j < n; j++){
    cin >> grid[i][j];
  }
 }
 
  for(int i = 0; i < n; i++){
    //temp[j] stores the minimum cost to reach (i, j)
    vector temp(n , 0);
    for(int j = 0; j < n; j++){
      if(i == 0 ){
          
        //Case (0, 0)
        if(j == 0){
          //There is no way to reach (0, 0). So the cost to
          //reach (0, 0) is dp[0][0] = grid[0][0]
          temp[j] = grid[i][j];
        }
        //Remaining values for 0th row
        else{
            //There is only 1 way to reach (i, j) for remaining values in 0th row i.e from left
            temp[j] = temp[j - 1] + grid[i][j];
        }
      }
      //Case (i, 0): first row
      else if(j == 0){
        //First column can be reached only from the cell above it
        temp[j] = dp[j] + grid[i][j];
      }
      //Case(i, j): remaining positions
      else{
        // (i, j) can be reached either from left : (i, j - 1) or up (i - 1, j)
        //We choose minimum of both
        temp[j] = min(dp[j], temp[j - 1]) + grid[i][j];
      }
 
  }
    dp = temp;
 }
 
 //Cost to reach the destination (n - 1, n - 1) is dp[n - 1][n - 1];
 cout << dp[n-1];
 return 0;
}