Given a 2D array grid[][] of size N * M, the value in grid[][] represents points that you can collect, if you collect any points from a particular cell then all the points from the adjacent row (i.e, i – 1 and i + 1) and adjacent column (i.e, j + 1 and j – 1) will get disappear. The task is to collect the maximum number of points from the grid.
Note: You can start collecting points from any cells in the matrix.
Examples:
Input: grid[][] = {{3, 8, 6, 9}, {9, 9, 1, 2}, {3, 9, 1, 7}}
Output: 33
Explanation: Collect points 8, 9, from row 1 and 9 and 7 from row 3.Input: grid[][] = {{12, 7, 6, 5}, {9, 9, 3, 1}, {9, 8, 1, 2}}
Output: 29
Approach (Using Dynamic Programming):
This problem can be divided into multiple smaller subproblems. The first subproblem involves finding the maximum value of points collected in each row while following the condition that no two consecutive cells in each row (i.e., grid[i][j + 1] and grid[i][j – 1]) are collected simultaneously. Store the results of this subproblem into another array and apply the same technique again to achieve the constraint that points cannot be collected from adjacent rows.
Steps to solve the problem:
- Iterate over each row of the grid and call a findMax() to find the maximum points that can be collected in each row by following the constraint that points at the adjacent column cells can’t be collected.
- Store the result of each row in an array (say dp[]).
- Again call the findMax() for the stored state in dp[], to find the maximum value that can be collected among all rows by following constraints that points at adjacent rows can’t be collected.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum valueint findMax(vector<int>& arr){ int n = arr.size(), result = 0; // Create dp of size n, where dp[i] // will store the maximum point // collected at ith index by following // the rule that no two consective // points can't be collected vector<int> dp(n); dp[0] = arr[0]; result = dp[0]; if (n <= 1) return result; dp[1] = max(arr[1], arr[0]); result = max(result, dp[1]); for (int i = 2; i < n; i++) { dp[i] = max(dp[i - 1], arr[i] + dp[i - 2]); result = max(result, dp[i]); } return result;}int solve(vector<vector<int> >& grid){ int m = grid.size(); // This will store the maximum points // collected by each row. vector<int> dp; // Find the maximum values obtained by // each row by following the constrain // that no two consective cell // of column can't be collected for (int i = 0; i < m; i++) { int val = findMax(grid[i]); dp.push_back(val); } // Again call the find1, as again we // have similar problem that no two // consective rows Can be collected return findMax(dp);}// Driver codeint main(){ vector<vector<int> > grid = { { 3, 8, 6, 9 }, { 9, 9, 1, 2 }, { 3, 9, 1, 7 } }; // Function Call int result = solve(grid); cout << result; return 0;} |
33
Time Complexity: O(N * M) where N is the number of rows and M is the number of columns
Auxiliary Space: O(max(N, M))
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
