Maximum Path Sum in The Matrix - 2D Dynamic Programming

My approach:

In this, we have a variable starting point and a variable ending point.

To solve it recursively we can easily convert it into a question of fixed-starting point and variable ending point.

My solution:

• Recursive

• Iterative

Code:

• Memoization

#include <bits/stdc++.h> 

int helper(vector<vector<int>> &matrix, int n, int m, int i, int j,vector<vector<int>> &dp){
    if(i>=n || j>=m || j<0){
        return -1e8;
    }

    if(i==n-1){
        return matrix[i][j];
    }

    if(dp[i][j]!=-1){
        return dp[i][j];
    }

    int down = helper(matrix,n,m,i+1,j,dp);
    int leftDia = helper(matrix,n,m,i+1,j-1,dp);
    int rightDia = helper(matrix,n,m,i+1,j+1,dp);

    dp[i][j] = max(down,max(leftDia,rightDia))+matrix[i][j];
    return max(down,max(leftDia,rightDia))+matrix[i][j];
}

int getMaxPathSum(vector<vector<int>> &matrix){
    int n = matrix.size();
    int m = matrix[0].size();

    vector<vector<int>> dp(n, vector<int>(m,-1));

    int maxi = -1e8;
    for(int j=0;j<m;j++){
        maxi = max(maxi, helper(matrix,n,m,0,j,dp));
    }

    return maxi;
}

• Tabulation

#include <bits/stdc++.h> 

int getMaxPathSum(vector<vector<int>> &matrix){
    int n = matrix.size();
    int m = matrix[0].size();

    vector<vector<int>> dp(n, vector<int>(m+1,INT_MIN));

    for(int i=0;i<m;i++){
        dp[0][i] = matrix[0][i];
        dp[0][m] = max(dp[0][m],dp[0][i]);
    }

    for(int i=1;i<n;i++){
        for(int j=0;j<m;j++){
            int up = dp[i-1][j];
            int leftDia = INT_MIN;
            int rightDia = INT_MIN;

            if(j!=0){
                leftDia = dp[i-1][j-1];
            }
            if(j!=m-1){
                rightDia = dp[i-1][j+1];
            }

            dp[i][j] = max(up, max(leftDia, rightDia))+matrix[i][j];
            dp[i][m] = max(dp[i][m], dp[i][j]);
        }
    }

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

Question Link:

https://www.codingninjas.com/studio/problems/maximum-path-sum-in-the-matrix_797998?source=youtube&campaign=striver_dp_videos&utm_source=youtube&utm_medium=affiliate&utm_campaign=striver_dp_videos&leftPanelTab=0

Similar Question:

https://www.codingninjas.com/studio/problems/minimum-falling-path-sum_893012