**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.