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
-
Start the traversal from the top right and top left column.
-
Check for all possible combinations and store the max value inside a variable.
-
If the current cell is out of bound return INT_MIN.
-
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: 42Time 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).
85+ registered