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.
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);intsolve(int i,int j,vector< vector<int>>&mat,vector<vector<int>>&dp){if(i==0&& j==0)return1;if(i<0|| j<0)return0;if(mat[i][j]==-1)return0;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;}intmazeObstacles(int n,int m, vector< vector<int>>&mat){// Write your code hereif(mat[0][0]==-1){return0;} vector<vector<int>>dp(n,vector<int>(m,-1));returnsolve(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>intsolve(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)return1e9;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);}intminSumPath(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));returnsolve(n-1,m-1,grid,dp);}
: Hey! is your brain fried of this blog? . Well what about a game with me?