SS3 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest

Author: Sandeep Singh
Tester: Md Shahid
Editorialist: Sandeep Singh

DIFFICULTY:

EASY

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given a matrix M[ ][ ] consisting of apples, find the maximum apples that can be collected on the way from the top-left cell to the bottom-right cell. You can only traverse down or right from a particular cell.

QUICK EXPLANATION:

The only way to reach a particular cell is from above or from left. So we take the one where we collected max apples. Add the max to the apples in that particular cell and we have the max apples that can be collected on reaching that cell. Doing this for each cell will finally give us the answer for the bottom right cell

EXPLANATION:

This is a very simple dynamic programming problem. Lets define a matrix dp[][] where dp[i][j] contains the max apples that can be collected on reaching the M[i][j] cell. Since the movements are restricted to down and right only, Ryuk will reach a particular cell either from the cell above it or the one to its left. Since we want to maximize the answer, we will select the one where we were able to collect the max apples and add that to the apples in the current cell and that will be the answer for that particular cell. The recurrence formula is as follows

dp[i][j]=M[i][j]+max(dp[i-1][j],dp[i][j-1]);

For base cases,
The answer for the top-left cell is the number of apples in it.
For all other cells in the top row, the answer is the apples in that cell plus the answer of the cell to its left since that is the only way to reach that cell.
For all other cells in the first column, the answer is the apples in that cell plus the answer of the cell above since that is the only way to reach that cell.

But instead of manually setting the base cases, we can use 1 based indexing for the matrix and set the answer to the 0^{th} row and column to 0. Then just apply the recurrence formula for the rest of the cells and print the answer for the bottom-right cell.

for(i=1;i<=N;i++){
		for(j=1;j<=N;j++)
			dp[i][j]=M[i][j]+max(dp[i-1][j],dp[i][j-1]);
	}

Time Complexity is O(N^2).

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int M[1005][1005];
ll dp[1005][1005];
void solve(){
	int N,i,j;
	cin>>N;
	memset(dp,0,sizeof(dp));
	
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
			cin>>M[i][j];
	
	for(i=1;i<=N;i++){
		for(j=1;j<=N;j++)
			dp[i][j]=M[i][j]+max(dp[i-1][j],dp[i][j-1]);
	}
	
	
	cout<<dp[N][N]<<endl;
}
int main() {

	//freopen("ip7.in", "r", stdin);
	//freopen("op7.out", "w", stdout);

	int T;
	cin>>T;
	while(T--)
		solve();
	return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
#define ll long long int 
using namespace std;
int main() {
    int T;
    cin>>T;
    while(T--){
        ll n; 
        cin>>n;
        ll A[n][n];
        for(ll i=0; i<n; i++)
            for(ll j=0; j<n; j++)
                cin>>A[i][j];
        ll dp[n+1][n+1];
        memset(dp,0, sizeof dp);
        for(ll i=0; i<n; i++){
            for(ll j=0; j<n; j++){
                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]) + A[i][j];
            }
        }
        cout<<dp[n][n]<<"\n";
    }
    return 0;
}
1 Like