Given a matrix grid[][] of order N*M with numbers 0-9 in the cells. The task is to find the maximum amount of money collected when two persons move from (0, 0) to (N-1, M-1) by moving only right and down. If both persons are at the same cell, then only one of them can pick the money at that location.
Examples:
Input:
1 1 1
1 0 1
1 1 1
Output: 8
Explanation: Let 1 denote the places where person 1 collects the money and 2 denote where person 2 does so, then a possible solution is
1 1 1
2 0 1
2 2 1Input:
0 9 9 3 3
2 9 3 3 3
0 3 3 3 3
4 1 1 1 1
Output: 52
Approach: The problem can be solved by using the recursion, by moving both the persons down and right in each of the cell and finding the maximum path sum in all the paths from (0, 0) to (N-1, M-1). So the idea is to find the cost of all possible paths and to find the maximum of them.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const static int MAXR = 20, MAXC = 20;int cache[MAXC][MAXR][MAXC][MAXR], dp[MAXC][MAXR][MAXC][MAXR];int n, m;vector<string> grid;// Function to find maximum money collected// when moving from (0, 0) to (N-1, M-1)int maxMoney(int x1, int y1, int x2, int y2){ // Out of bounds of grid if (x1 >= n || y1 >= m || x2 >= n || y2 >= m) return 0; if (cache[x1][y1][x2][y2] != 0) return dp[x1][y1][x2][y2]; // Mark state as visited cache[x1][y1][x2][y2] = 1; // Collect money from the grid cell int money = grid[y1][x1] - '0'; if (x1 != x2 || y1 != y2) money += grid[y2][x2] - '0'; // Take maximum of all possibilities return dp[x1][y1][x2][y2] = money + max( max(maxMoney(x1 + 1, y1, x2 + 1, y2), maxMoney(x1, y1 + 1, x2 + 1, y2)), max(maxMoney(x1 + 1, y1, x2, y2 + 1), maxMoney(x1, y1 + 1, x2, y2 + 1)));}// Driver Codeint32_t main(){ // Given Input n = 3; m = 3; grid.push_back("111"); grid.push_back("101"); grid.push_back("111"); // Function Call cout << maxMoney(0, 0, 0, 0); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{static int MAXR = 20, MAXC = 20;static int [][][][]cache = new int[MAXC][MAXR][MAXC][MAXR];static int [][][][]dp = new int[MAXC][MAXR][MAXC][MAXR];static int n, m;static Vector<String> grid = new Vector<String>();// Function to find maximum money collected// when moving from (0, 0) to (N-1, M-1)static int maxMoney(int x1, int y1, int x2, int y2){ // Out of bounds of grid if (x1 >= n || y1 >= m || x2 >= n || y2 >= m) return 0; if (cache[x1][y1][x2][y2] != 0) return dp[x1][y1][x2][y2]; // Mark state as visited cache[x1][y1][x2][y2] = 1; // Collect money from the grid cell int money = grid.get(y1).charAt(x1)- '0'; if (x1 != x2 || y1 != y2) money += grid.get(y2).charAt(x2) - '0'; // Take maximum of all possibilities return dp[x1][y1][x2][y2] = money + Math.max( Math.max(maxMoney(x1 + 1, y1, x2 + 1, y2), maxMoney(x1, y1 + 1, x2 + 1, y2)), Math.max(maxMoney(x1 + 1, y1, x2, y2 + 1), maxMoney(x1, y1 + 1, x2, y2 + 1)));}// Driver Codepublic static void main(String[] args){ // Given Input n = 3; m = 3; grid.add("111"); grid.add("101"); grid.add("111"); // Function Call System.out.print(maxMoney(0, 0, 0, 0));}}// This code is contributed by Princi Singh |
Python3
# Python3 program for the above approachMAXR, MAXC = 20, 20cache = [[[[0 for i in range(MAXR)] for j in range(MAXC)] for k in range(MAXR)] for l in range(MAXC)]dp = [[[[0 for i in range(MAXR)] for j in range(MAXC)] for k in range(MAXR)] for l in range(MAXC)]grid = []# Function to find maximum money collected# when moving from (0, 0) to (N-1, M-1)def maxMoney(x1, y1, x2, y2): # Out of bounds of grid if (x1 >= n or y1 >= m or x2 >= n or y2 >= m): return 0 if (cache[x1][y1][x2][y2] != 0): return dp[x1][y1][x2][y2] # Mark state as visited cache[x1][y1][x2][y2] = 1 # Collect money from the grid cell money = ord(grid[y1][x1]) - ord('0') if (x1 != x2 or y1 != y2): money += ord(grid[y2][x2]) - ord('0') dp[x1][y1][x2][y2] = money + max(max(maxMoney(x1 + 1, y1, x2 + 1, y2), maxMoney(x1, y1 + 1, x2 + 1, y2)), max(maxMoney(x1 + 1, y1, x2, y2 + 1), maxMoney(x1, y1 + 1, x2, y2 + 1))) # Take maximum of all possibilities return dp[x1][y1][x2][y2]# Given Inputn = 3m = 3grid.append("111")grid.append("101")grid.append("111")# Function Callprint(maxMoney(0, 0, 0, 0))# This code is contributed by suresh07. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{static int MAXR = 20, MAXC = 20;static int [,,,]cache = new int[MAXC,MAXR,MAXC,MAXR];static int [,,,]dp = new int[MAXC,MAXR,MAXC,MAXR];static int n, m;static List<String> grid = new List<String>();// Function to find maximum money collected// when moving from (0, 0) to (N-1, M-1)static int maxMoney(int x1, int y1, int x2, int y2){ // Out of bounds of grid if (x1 >= n || y1 >= m || x2 >= n || y2 >= m) return 0; if (cache[x1,y1,x2,y2] != 0) return dp[x1,y1,x2,y2]; // Mark state as visited cache[x1,y1,x2,y2] = 1; // Collect money from the grid cell int money = grid[y1][x1]- '0'; if (x1 != x2 || y1 != y2) money += grid[y2][x2] - '0'; // Take maximum of all possibilities return dp[x1,y1,x2,y2] = money + Math.Max( Math.Max(maxMoney(x1 + 1, y1, x2 + 1, y2), maxMoney(x1, y1 + 1, x2 + 1, y2)), Math.Max(maxMoney(x1 + 1, y1, x2, y2 + 1), maxMoney(x1, y1 + 1, x2, y2 + 1)));}// Driver Codepublic static void Main(String[] args){ // Given Input n = 3; m = 3; grid.Add("111"); grid.Add("101"); grid.Add("111"); // Function Call Console.Write(maxMoney(0, 0, 0, 0));}}// This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program for the above approach let MAXR = 20, MAXC = 20; let cache = new Array(MAXC); let dp = new Array(MAXC); for(let i = 0; i < MAXR; i++) { dp[i] = new Array(MAXR); cache[i] = new Array(MAXR); for(let j = 0; j < MAXC; j++) { dp[i][j] = new Array(MAXC); cache[i][j] = new Array(MAXC); for(let k = 0; k < MAXR; k++) { dp[i][j][k] = new Array(MAXR); cache[i][j][k] = new Array(MAXR); for(let l = 0; l < MAXR; l++) { dp[i][j][k][l] = 0; cache[i][j][k][l] = 0; } } } } let n, m; let grid = []; // Function to find maximum money collected // when moving from (0, 0) to (N-1, M-1) function maxMoney(x1, y1, x2, y2) { // Out of bounds of grid if (x1 >= n || y1 >= m || x2 >= n || y2 >= m) return 0; if (cache[x1][y1][x2][y2] != 0) return dp[x1][y1][x2][y2]; // Mark state as visited cache[x1][y1][x2][y2] = 1; // Collect money from the grid cell let money = grid[y1][x1]- '0'; if (x1 != x2 || y1 != y2) money += grid[y2][x2] - '0'; // Take maximum of all possibilities dp[x1][y1][x2][y2] = money + Math.max( Math.max(maxMoney(x1 + 1, y1, x2 + 1, y2), maxMoney(x1, y1 + 1, x2 + 1, y2)), Math.max(maxMoney(x1 + 1, y1, x2, y2 + 1), maxMoney(x1, y1 + 1, x2, y2 + 1))); return dp[x1][y1][x2][y2]; } // Given Input n = 3; m = 3; grid.push("111"); grid.push("101"); grid.push("111"); // Function Call document.write(maxMoney(0, 0, 0, 0));// This code is contributed by divyeshrabadiya07.</script> |
Output
8
Time Complexity: O(2N*2M)
Auxiliary Space: O((N*M)2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
