---

title: 'DP problem set-4' topic : 'dynamic-programming' id: 4 description: 'Dynamic programming problem set of 2D dp. problems - Unique Paths II and Minimum Path Sum' subtopic: ['2d-dp']

DP problem set - 4

Summary for the blog ⌨️⌨️ In this blog of Dynamic programming, we will discuss 2d dp problems, we will see how to tackle these problems, intuition and the codes.

Sl No	Leetcode problems/ Algorithms	Link
1	Unique Paths II	Problem 1
2	Minimum Path Sum	Problem 2

Problem No - 1 [Unique Paths II]

Intuition :-

• This is similar problem to unique paths, except here there is obstructions along our path.
• Hence we will start from bottom right, and travel to reach top left.
• We will iterate the matrix in the recursion with a index i and j which represents row and columns respectively.
• The base case would be if we reach top left position we would return 1. if the indexes i and j go out of bound ie i or j becomes less than 0 we would return 0.
• if at any index, the value is -1. we would return 0 (as it is an obstruction).
• At every position we can either move to left or upwards. we will explore both the possibilities. and return the sum of both.
• In memoisation we will take a 2D array of size nxm to store the previously calculated number of paths.
• you can explore other technique called tabulation as well.

int mod =int(1e9+7);

int solve(int i,int j,vector< vector< int> > &mat,vector<vector<int>>&dp){
    if(i==0 && j==0) return 1;
    if(i<0 || j<0) return 0;
    if(mat[i][j]==-1) return 0;

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

    int up = solve(i-1, j, mat,dp)%mod;
    int left = solve(i, j-1, mat,dp)%mod;

    return dp[i][j]= (left+up)%mod;
}

int mazeObstacles(int n, int m, vector< vector< int> > &mat) {
    // Write your code here
    if(mat[0][0]==-1){
        return 0;
    }
    vector<vector<int>>dp(n,vector<int>(m,-1));
    return solve(n-1,m-1,mat,dp);
}

---

Problem No - 2 [Minimum Path Sum]

Intuition :-

• Here the problem is very simple, we just need to travel from (0,0) to (m-1,n-1). and the only move possible is down and right. and we need to return the minimum cost among all the path.
• We would solve the problem in quite opposite way, ie we will go from bottom right to top left.
• The base case would be if we reach top left position we would return grid[0][0]. if the indexes i and j go out of bound ie i or j becomes less than 0 we would return ie9 (ie a large value so that it won’t be included in the path).
• In every index we have 2 possibilities , ie either go left or go up.
• We would return the minimum of both the possibilities, as we are asked to return the minimum path sum
• memoisation technique similar to previous problem is implemented.

#include <bits/stdc++.h> 

int solve(int i,int j,vector< vector< int> > &grid,vector<vector<int>>&dp){
    if(i==0 && j==0) return grid[0][0];
    if(i<0 || j<0) return 1e9;

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

    int up =grid[i][j]+ solve(i-1, j, grid,dp);
    int left =grid[i][j]+ solve(i, j-1, grid,dp);

    return dp[i][j]= min(left,up);
}

int minSumPath(vector<vector<int>> &grid) {
    // Write your code here.
    int n =grid.size();
    int m =grid[0].size();
     vector<vector<int>>dp(n,vector<int>(m,-1));
    return solve(n-1,m-1,grid,dp);
}

---