Problem Statement

Given a NxN matrix of positive integers. There are only three possible moves from a cell Matrix[r][c].

1. Matrix [r+1] [c]
2. Matrix [r+1] [c-1]
3. Matrix [r+1] [c+1]

​Starting from any column in row 0, return the largest sum of any of the paths up to row N-1.

Example 1:

Input: N = 2
Matrix = {{348, 391},
          {618, 193}}
Output: 1009
Explaination: The best path is 391 -> 618.
It gives the sum = 1009.

Problem Link

Maximum path sum in matrix | Practice | GeeksforGeeks

Code

class Solution{
public:
vector<vector<int>> dp;
    int maximumPath(int N, vector<vector<int>> Matrix)
    {
       
      
       dp.resize(N,vector<int>(N,-1));
       int res = 0;    
       for(int i=0;i<N;i++)
       {
           dp[0][i] = dfs(Matrix,0,i);
           res = max(res,dp[0][i]);
       }
           
       
       return res;
        
    }
    int dfs(vector<vector<int>> Matrix,int r,int c)
    {
        int N = Matrix.size();
        if(r<0||r>N-1||c<0||c>N-1)
        return 0;
        
        if(r==N-1)
        return dp[r][c] =  Matrix[r][c];
        
        if(dp[r][c]!=-1)
        return dp[r][c];
        
        
        return dp[r][c] = Matrix[r][c] + max(dfs(Matrix,r+1,c),max(dfs(Matrix,r+1,c-1),dfs(Matrix,r+1,c+1)));
        
    }
};
// Time Complexity : O(n^2)
// Space Complexity : O(n^2)