Two players X and Y are playing a game in which there are pots of gold arranged in a line, each containing some gold coins. They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player who has a higher number of coins at the end. The objective is to maximize the number of coins collected by X, assuming Y also plays optimally. Return the maximum coins X could get while playing the game. Initially, X starts the game.
Examples:
Input: N = 4, Q[] = {8, 15, 3, 7}
Output: 22
Explanation: Player X starts and picks 7. Player Y picks the pot containing 8. Player X picks the pot containing 15. Player Y picks 3. Total coins collected by X = 7 + 15 = 22.Input:N = 4, A[] = {2, 2, 2, 2}
Output: 4
Approach: This can be solved with the following idea:
Using Dynamic programming as it has an optimum substructure and overlapping subproblems.
Steps involved in the implementation of code:
- Declare a static 1002 x 1002 2D integer array with the name dp.
- Add a public static method called “getMaxCoins” that accepts an integer array called “coins, ” together with the parameters “integer start” and “integer end, ” and returns an integer result.
- Return zero if start exceeds finish.
- Return dp[start][end] if dp[start][end] is not equal to -1.
- Create the variables option1 and option2 as two integers.
- GetMaxCoins with parameters coins, start+1, end-1, and getMaxCoins with parameters coins, start, end-2 are called recursively with the option1 set to coins[end] plus the minimum value in between.
- Option 2 should be set to coins[start] plus the minimum value in between calls to the recursive functions getMaxCoins with the arguments coins, start+2, end, and getMaxCoins with the arguments coins, start+1, end-1.
- Set the highest value possible between options 1 and 2 for dp[start][end].
- Bring back dp[start][end].
- Make a public static method called maxCoins that receives an integer value as a return parameter and accepts integer array coins and an integer n as input arguments.
- To add -1 values to the dp array, use a nested loop.
- Return the value of the getMaxCoins method with parameters coins, 0, n-1
Below is the code implementation of the above approach:
C++14
// C++ code of the above approach#include <bits/stdc++.h>using namespace std;int dp[1002][1002];// Returns the maximum coins that// can be collected from start to endint getMaxCoins(int coins[], int start, int end){ // Base case: When start index is // greater than end index if (start > end) { return 0; } // If we have already computed the // solution for this sub-problem if (dp[start][end] != -1) { return dp[start][end]; } // Case 1: Choose the last coin, // then we can choose between the // first and second-last coins int option1 = coins[end] + min(getMaxCoins(coins, start + 1, end - 1), getMaxCoins(coins, start, end - 2)); // Case 2: Choose the first coin, // then we can choose between the // second and last coins int option2 = coins[start] + min(getMaxCoins(coins, start + 2, end), getMaxCoins(coins, start + 1, end - 1)); // Store the maximum coins that // can be collected from start // to end dp[start][end] = max(option1, option2); return dp[start][end];}int maxCoins(int coins[], int n){ // Initialize the DP array with -1 memset(dp, -1, sizeof(dp)); return getMaxCoins(coins, 0, n - 1);}// Driver codeint main(){ int coins[] = { 8, 15, 3, 7 }; int n = sizeof(coins) / sizeof(coins[0]); int maxCoin = maxCoins(coins, n); // Function call cout << maxCoin << endl; return 0;} |
Java
// Java code of the above approachimport java.util.*;class GfG { public static int dp[][] = new int[1002][1002]; // Returns the maximum coins that // can be collected from start to end public static int getMaxCoins(int[] coins, int start, int end) { // Base case: When start index is // greater than end index if (start > end) { return 0; } // If we have already computed the // solution for this sub-problem if (dp[start][end] != -1) { return dp[start][end]; } // Case 1: Choose the last coin, // then we can choose between the // first and second-last coins int option1 = coins[end] + Math.min( getMaxCoins(coins, start + 1, end - 1), getMaxCoins(coins, start, end - 2)); // Case 2: Choose the first coin, // then we can choose between the // second and last coins int option2 = coins[start] + Math.min( getMaxCoins(coins, start + 2, end), getMaxCoins(coins, start + 1, end - 1)); // Store the maximum coins that // can be collected from start // to end dp[start][end] = Math.max(option1, option2); return dp[start][end]; } public static int maxCoins(int[] coins, int n) { // Initialize the DP array with -1 for (int i = 0; i < 1001; i++) { Arrays.fill(dp[i], -1); } return getMaxCoins(coins, 0, n - 1); } // Driver code public static void main(String args[]) { int[] coins = { 8, 15, 3, 7 }; int n = coins.length; int maxCoins = maxCoins(coins, n); // Function call System.out.println(maxCoins); }} |
Python3
class GfG: dp = [[-1 for i in range(1002)] for j in range(1002)] # Returns the maximum coins that # can be collected from start to end def getMaxCoins(self, coins, start, end): # Base case: When start index is # greater than end index if start > end: return 0 # If we have already computed the # solution for this sub-problem if self.dp[start][end] != -1: return self.dp[start][end] # Case 1: Choose the last coin, # then we can choose between the # first and second-last coins option1 = coins[end] + min(self.getMaxCoins(coins, start + 1, end - 1), self.getMaxCoins(coins, start, end - 2)) # Case 2: Choose the first coin, # then we can choose between the # second and last coins option2 = coins[start] + min(self.getMaxCoins(coins, start + 2, end), self.getMaxCoins(coins, start + 1, end - 1)) # Store the maximum coins that # can be collected from start # to end self.dp[start][end] = max(option1, option2) return self.dp[start][end] def maxCoins(self, coins, n): # Initialize the DP array with -1 for i in range(1001): for j in range(1001): self.dp[i][j] = -1 return self.getMaxCoins(coins, 0, n - 1)# Driver codeif __name__ == '__main__': coins = [8, 15, 3, 7] n = len(coins) gfg = GfG() maxCoins = gfg.maxCoins(coins, n) # Function call print(maxCoins) |
C#
using System;class GFG { public static int[,] dp = new int[1002, 1002]; // Returns the maximum coins that can be collected from start to end public static int getMaxCoins(int[] coins, int start, int end) { // Base case: When start index is greater than end index if (start > end) { return 0; } // If we have already computed the solution for this sub-problem if (dp[start, end] != -1) { return dp[start, end]; } // Case 1: Choose the last coin, then we can choose // between the first and second-last coins int option1 = coins[end] + Math.Min(getMaxCoins(coins, start + 1, end - 1), getMaxCoins(coins, start, end - 2)); // Case 2: Choose the first coin, // then we can choose between the second and last coins int option2 = coins[start] + Math.Min(getMaxCoins(coins, start + 2, end), getMaxCoins(coins, start + 1, end - 1)); // Store the maximum coins that can be collected from start to end dp[start, end] = Math.Max(option1, option2); return dp[start, end]; } public static int maxCoins(int[] coins, int n) { // Initialize the DP array with -1 for (int i = 0; i < 1001; i++) { for (int j = 0; j < 1001; j++) { dp[i,j] = -1; } } return getMaxCoins(coins, 0, n - 1); } // Driver code public static void Main() { int[] coins = {8, 15, 3, 7}; int n = coins.Length; int mxCoins = maxCoins(coins, n); // Function call Console.WriteLine(mxCoins); }} |
Javascript
// JavaScript code of the above approach// Returns the maximum coins that// can be collected from start to endfunction getMaxCoins(coins, start, end, dp) { // Base case: When start index is // greater than end index if (start > end) { return 0; } // If we have already computed the // solution for this sub-problem if (dp[start][end] != -1) { return dp[start][end]; } // Case 1: Choose the last coin, // then we can choose between the // first and second-last coins let option1 = coins[end] + Math.min(getMaxCoins(coins, start + 1, end - 1, dp), getMaxCoins(coins, start, end - 2, dp)); // Case 2: Choose the first coin, // then we can choose between the // second and last coins let option2 = coins[start] + Math.min(getMaxCoins(coins, start + 2, end, dp), getMaxCoins(coins, start + 1, end - 1, dp)); // Store the maximum coins that // can be collected from start // to end dp[start][end] = Math.max(option1, option2); return dp[start][end];}function maxCoins(coins, n) { let dp = []; // Initialize the DP array with -1 for (let i = 0; i <= n; i++) { dp[i] = Array(n).fill(-1); } return getMaxCoins(coins, 0, n - 1, dp);}// Driver codelet coins = [ 8, 15, 3, 7 ];let n = coins.length;let maxCoin = maxCoins(coins, n);// Function callconsole.log(maxCoin);// This code is contributed by prasad264 |
Output
22
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a DP of size n*n to store the solution of the subproblems .
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
- Return the final solution stored in dp[0][n – 1].
Implementation :
C++
// C++ code of the above approach#include <bits/stdc++.h>using namespace std;// Returns the maximum coins that// can be collected from start to endint maxCoins(int coins[], int n) { // Base case if (n == 0) return 0; //intialize dp int dp[n][n]; //iterate over subproblems for (int len = 1; len <= n; len++) { for (int start = 0; start <= n - len; start++) { int end = start + len - 1; int x = ((start + 2 <= end) ? dp[start + 2][end] : 0); int y = ((start + 1 <= end - 1) ? dp[start + 1][end - 1] : 0); int z = ((start <= end - 2) ? dp[start][end - 2] : 0); //current value dp[start][end] = max(coins[start] + min(x, y), coins[end] + min(y, z)); } } //return answer return dp[0][n - 1];}//Driver Codeint main() { int coins[] = { 8, 15, 3, 7 }; int n = sizeof(coins) / sizeof(coins[0]); int maxCoin = maxCoins(coins, n); cout << maxCoin << endl; return 0;} |
Python3
# Python code of the above approachdef maxCoins(coins, n): # Base case if n == 0: return 0 # intialize dp dp = [[0 for j in range(n)] for i in range(n)] # iterate over subproblems for length in range(1, n+1): for start in range(n - length + 1): end = start + length - 1 x = dp[start + 2][end] if start + 2 <= end else 0 y = dp[start + 1][end - 1] if start + 1 <= end - 1 else 0 z = dp[start][end - 2] if start <= end - 2 else 0 # current value dp[start][end] = max(coins[start] + min(x, y), coins[end] + min(y, z)) # return answer return dp[0][n - 1]# Driver Codecoins = [8, 15, 3, 7]n = len(coins)maxCoin = maxCoins(coins, n)print(maxCoin)# This code is contributed by Sakshi |
Output
22
Time Complexity: O(N^2)
Auxiliary Space: O(N^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!
