Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Optimized Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Frequently Asked Questions
4.1.
What is dynamic programming in simple words?
4.2.
What are the two applications of dynamic programming?
4.3.
What is recursion in programming?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Collect Maximum Points in a Grid using Two Traversals

Author Harsh
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Every big company asks at least 1 or 2 programming questions related to Dynamic Programming. Having a good knowledge of DP will help you to crack those big companies.

In this blog, we will be solving a problem related to dynamic programming.

Problem Statement

Ninja has given you a matrix of size “n x m” and each cell in the matrix represents a ninja point. Your task is to collect the maximum number of ninja points using two traversals.

If we consider R and C as the row size and column size for our matrix then the condition for the traversals are:

  • The first traversal starts from the cell (0, 0) and ends at cell (R-1, 0). Whereas the second traversal starts from the cell (0, C-1) and ends at cell (R-1, C-1).
  • We can move in three directions only i.e (i+1, j+1), (i+1, j), and (i+1, j-1).
  • A traversal obtains all points of a cell that it goes through. If one traversal has previously collected points for a cell, the other traversal will not receive any points if it traverses that cell again.

Sample Examples

Input

Output

Max Collection: 42

 

Explanation

 

 

 

Example 2

 

Input

Output

Max Collection: 31

 

Explanation

 

 

 

Approach

Traverse the matrix and collect all the points trying all possible combinations from where we can reach at the desired location after that we can select the best possible combination of traversal through which we are getting the maximum sum. And instead of traversing one by one we can do both of  the traversal at the same time and select the best combination that is giving us the maximum sum.

Algorithm

  1. Start the traversal from the top right and top left column.
     
  2. Check for all possible combinations and store the max value inside a variable.
     
  3. If the current cell is out of bound return INT_MIN.
     
  4. Return the final ans if we reach our final destination.
     

Implementation in C++

#include<bits/stdc++.h>
using namespace std;


int collectMax(vector<vector<int>>& grid, int x, int y1, int y2) {
    int ROW = grid.size();
    int COL = grid[0].size();


// Returning int_min if we are at invalid cell
if ((x < 0 || x >= ROW || y1 < 0 || y1 >= COL || y2 < 0 || y2 >= COL)) return INT_MIN;


// Reached the destination
if (x == ROW-1 && y1 == 0 && y2 == COL-1)
return (y1 == y2)? grid[x][y1]: grid[x][y1] + grid[x][y2];


// If both traversals reached at last row but not at the required column
if (x == ROW-1) return INT_MIN;


// Initializing result for current subproblem
int result = INT_MIN;


// Storing current cell's value
int currVal = (y1 == y2) ? grid[x][y1]: grid[x][y1] + grid[x][y2];


// check all possible solutions to get the maximum sum
result = max(result, currVal + collectMax(grid, x+1, y1, y2-1));
result = max(result, currVal + collectMax(grid, x+1, y1, y2+1));
result = max(result, currVal + collectMax(grid, x+1, y1, y2));
result = max(result, currVal + collectMax(grid, x+1, y1-1, y2));
result = max(result, currVal + collectMax(grid, x+1, y1-1, y2-1));
result = max(result, currVal + collectMax(grid, x+1, y1-1, y2+1));
result = max(result, currVal + collectMax(grid, x+1, y1+1, y2));
result = max(result, currVal + collectMax(grid, x+1, y1+1, y2-1));
result = max(result, currVal + collectMax(grid, x+1, y1+1, y2+1));


    // returning the result
return result;
}


int main()
{
    // input array
    cout << "Enter size of row & column: ";
    int row = 0, col = 0;
    cin >> row >> col;


    // matrix
    vector<vector<int>> grid(row, vector<int>(col));
    cout << "Enter elements: \n";
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            cin >> grid[i][j];
        }
    }


    // printing the result
cout << "Max Collection: " << collectMax(grid, 0, 0, col-1) << endl;
return 0;
}

 

Input

Enter size of row & column: 4 5
Enter elements: 
1 2 4 5 3
3 5 1 7 8
1 2 2 7 8
9 3 2 1 6

 

Output

Max Collection: 42

Time Complexity

As we are checking for all the possible combinations and some of the subproblems are rechecked. So, The time complexity is exponential.

Space Complexity

We are not using any extra space so space complexity is O(1).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

We can optimize the above approach by using the Memoization technique of dynamic programming. As there were some subproblems overlapping. So, in this approach, we will store the result of all subproblems and if it occurs again we’ll simply look into our storage and return the stored value.

Algorithm

  1. Start the traversal from top right and top left column.
     
  2. Check for all possible combinations and store the max value inside a variable.
     
  3. Check if the subproblem is already solved or not using DP array. If it is solved then return the result else continue.
     
  4. If the current cell is out of range return INT_MIN.
     
  5. Store the result in DP array and Return the final ans.
     

Implementation in C++

#include<bits/stdc++.h>
using namespace std;


int collectMax(vector<vector<int>> grid,vector<vector<vector<int>>> &dp, int x, int y1, int y2) {
    
    int ROW = grid.size();
    int COL = grid[0].size();


// Returning int_min if we are at invalid cell
if (x < 0 || x >= ROW || y1 < 0 || y1 >= COL || y2 < 0 || y2 >= COL) return INT_MIN;


// Reached the destination
if (x == ROW-1 && y1 == 0 && y2 == COL-1)
return (y1 == y2)? grid[x][y1]: grid[x][y1] + grid[x][y2];


// If both traversals reached at last row but not at the required column
if (x == ROW-1) return INT_MIN;


    // checking if the subproblem is already solved or not
    if (dp[x][y1][y2] != -1) return dp[x][y1][y2];


// Initializing result for current subproblem
int result = INT_MIN;


// Storing current cell's value
int currVal = (y1 == y2) ? grid[x][y1]: grid[x][y1] + grid[x][y2];


// check all possible solutions to get the maximum sum
result = max(result, currVal + collectMax(grid, dp, x+1, y1, y2-1));
result = max(result, currVal + collectMax(grid, dp, x+1, y1, y2+1));
result = max(result, currVal + collectMax(grid, dp, x+1, y1, y2));
result = max(result, currVal + collectMax(grid, dp, x+1, y1-1, y2));
result = max(result, currVal + collectMax(grid, dp, x+1, y1-1, y2-1));
result = max(result, currVal + collectMax(grid, dp, x+1, y1-1, y2+1));
result = max(result, currVal + collectMax(grid, dp, x+1, y1+1, y2));
result = max(result, currVal + collectMax(grid, dp, x+1, y1+1, y2-1));
result = max(result, currVal + collectMax(grid, dp, x+1, y1+1, y2+1));


    // returning the result
return (dp[x][y1][y2] = result);
}


int main()
{
    // input array
    cout << "Enter size of row & column: ";
    int row = 0, col = 0;
    cin >> row >> col;


    // matrix
    vector<vector<int>> grid(row, vector<int>(col));
    cout << "Enter elements: \n";
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            cin >> grid[i][j];
        }
    }
    
    // dp
    vector<vector<vector<int>>> dp(row, vector<vector<int>>(col, vector<int>(col, -1)));


    // printing the result
cout << "Max Collection: " << collectMax(grid, dp, 0, 0, col-1) << endl;
return 0;
}

 

Input

Enter size of row & column: 4 5
Enter elements: 
1 2 4 5 3
3 5 1 7 8
1 2 2 7 8
9 3 2 1 6

 

Output

Max Collection: 42

Time Complexity

There are total N*M^2 states. So, the Time complexity is O(NM^2).

Space Complexity

As we are using a dynamic programming array to store the result. So, the overall space complexity of our program is O(NM^2).

Check out this problem - Count Ways To Reach The Nth Stair 

Frequently Asked Questions

What is dynamic programming in simple words?

Dynamic Programming is a computer programming technique that aids in the effective solution of a class of problems with overlapping subproblems and optimal substructure. It is a technique that divides problems into sub-problems and saves the result for later use, eliminating the need to compute the result again.

 

What are the two applications of dynamic programming?

Dynamic programming is applicable in graph theory, game theory and in many more fields.

 

What is recursion in programming?

Recursion is a programming approach in computer science that uses a function or algorithm that calls itself one or more times until a specific condition is fulfilled, at which point the rest of each iteration is processed from the latest one called to the first.

Conclusion

In this article, we have discussed a question related to dynamic programming. First, we solved the question without using the dynamic programming approach then we implemented dynamic programming in the same program. We hope that this blog has enhanced your knowledge and cleared all of your doubts regarding the above question. Want to learn more?, check out our articles on our Website

Recommended problems -

 

You can also visit Guided Path on Coding Ninjas Studio to upskill yourself in Competitive ProgrammingData Structures and AlgorithmsSystem DesignJavaScript, and many more! You can also check Interview Experiences and Interview Preparation Resources if you are interested in cracking the technical interviews at top Product-based companies like Amazon, Microsoft, Uber, etc.

Upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and more with our Coding Ninjas Studio Guided Path.

Do upvote the blogs if you find it helpful and engaging!

Happy Learning!

Previous article
Check for Binary Search Tree
Next article
Minimum Number of Taps to Open to Water a Garden
Live masterclass