PROBLEM LINK:
Author :alkama_123
Tester : maazbinasad3
Editorialist : alkama_123
DIFFICULTY :
Easy to Medium
PREREQUISITES :
Dynamic Programming
PROBLEM :
Chef wants to go to his home and there is a grid on the way. (The grid is a Square Matrix of size nn ).
And chef is Currently at the UpperLeftmost point (i.e. at 0,0) and his home is at the lower rightmost point (i.e. at n,n).
he is Restricted to move only either Right or Bottom.
Given the traveling Cost of each cell (means chef has to pay that amount to go from that cell) of the grid, the chef wants to reach his home and he has limited money,
your job is to tell the chef how much minimum money should chef take so that he will reach his home despite the choosen path
QUICK EXPLANATION
Find the maximum cost out of the possible two possible path for each move(step) taken by chef
sum(y, x) = max(sum(y, x−1),sum(y−1, x))+value[y][x] ,where x,y are indexes of grid
EXPLANATION :
In this we will discuss Top Down (Tabulation ) Approach…
→ first make a dp Mtrix (2d array) for storing the answer of each value of n starting from 0 to n and initialize with 0th row and 0th column to 0;
→Now for each step find the maximum cost out of both the possible path . like this
dp[i][j] = max(dp[i][j-1],dp[i-1][j]) +input[i-1][j-1];
→ Now Print the Value at nth index of dp array
TIME COMPLEXITY :
For considering test case O(T*N^2)
T= no of test case and
N=
SOLUTIONS :
Editorialist’s Solution
#include <bits/stdc++.h>
using namespace std;
int32_t main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int matrix[n][n];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>matrix[i][j];
}
}
int sum[n+1][n+1];
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
if(i==0 || j==0)sum[i][j]=0;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
sum[i][j] = max(sum[i][j-1],sum[i-1][j]) +matrix[i-1][j-1];
}
}
cout<<sum[n][n]<<endl;
}
return 0;
}
Feel Free to share and discuss your approach here.