Coins in a line problem

Coins in a Line

Question Link

Problem Statement :

There are A coins (Assume A is even) in a line.

Two players take turns to take a coin from one of the ends of the line until there are no more coins left.

The player with the larger amount of money wins, Assume that you go first.

Return the maximum amount of money you can win.

NOTE:

  • You can assume that opponent is clever and plays optimally.

Input Values:

an integer array A.

Output Value:

The maximum amount of money you can win.

Constraints:

1 <= length(A) <= 500

1 <= A[i] <= 10^5

Examples:

Example 1:

Input : A = [1, 2, 3, 4].
Output : 6
Explanation : 
 You      : Pick 4
 Opponent : Pick 3
 You      : Pick 2
 Opponent : Pick 1

Total money with you : 4 + 2 = 6

Example 2:

Input : A = [5, 4, 8, 10]
Output : 15
Explanation : 
 You      : Pick 10
 Opponent : Pick 8
 You      : Pick 5
 Opponent : Pick 4

Total money with you : 10 + 5 = 15

👉Naive approach:-

IThe naive approach for this problem involves simulating all possible moves and choosing the one that maximizes the total amount of money. We can define a recursive function, maxMoneyHelper, that considers both ends of the line and explores the possibilities of choosing a coin from either end. Each player aims to maximize their total amount of money, considering that the opponent plays optimally.

Pseudocode:-

  • Define a function maxMoney that takes the array of coins A and its length n as input.
  • Define a helper function maxMoneyHelper(left, right) that takes the indices of the current subarray.
    • If left > right, return 0 (no coins left in the subarray).
    • Calculate the amount of money obtained by choosing the left coin: leftAmount = A[left] + min(maxMoneyHelper(left + 2, right), maxMoneyHelper(left + 1, right - 1)).
    • Calculate the amount of money obtained by choosing the right coin: rightAmount = A[right] + min(maxMoneyHelper(left + 1, right - 1), maxMoneyHelper(left, right - 2)).
    • Return the maximum of leftAmount and rightAmount.
  • The result is obtained by calling maxMoneyHelper(0, n - 1)

👉Dynamic Programming Approach:-

The dynamic programming approach involves memoizing the results of subproblems to avoid redundant calculations. We can use a 2D array dp to store the results of subproblems, where dp[i][j] represents the maximum amount of money that can be obtained from the subarray A[i:j]. The recursion involves considering both ends of the line and choosing the move that maximizes the total amount of money

Pseudocode:-

Pseudocode (Dynamic Programming in words):

  • Initialize a 2D array dp of size n x n and set all values to -1.
  • Define a function maxMoneyDP that takes the array of coins A and its length n as input.
  • Define a helper function maxMoneyHelper(left, right) that takes the indices of the current subarray.
    • If left > right, return 0 (no coins left in the subarray).
    • If dp[left][right] is not -1, return dp[left][right] (memoization).
    • Calculate the amount of money obtained by choosing the left coin: leftAmount = A[left] + min(maxMoneyHelper(left + 2, right), maxMoneyHelper(left + 1, right - 1)).
    • Calculate the amount of money obtained by choosing the right coin: rightAmount = A[right] + min(maxMoneyHelper(left + 1, right - 1), maxMoneyHelper(left, right - 2)).
    • Update dp[left][right] with the maximum of leftAmount and rightAmount.
    • Return the updated dp[left][right].
  • The result is obtained by calling maxMoneyHelper(0, n - 1).

Code for the problem:-

Java Code

public class MaxMoneyGame{

// Naive approach

public static int maxMoneyNaive(int[] A) {
        int n = A.length;
        return maxMoneyHelper(A, 0, n - 1);
    }

    private static int maxMoneyHelper(int[] A, int left, int right) {
        if (left > right) {
            return 0;
        }

        int leftAmount = A[left] + Math.min(maxMoneyHelper(A, left + 2, right), maxMoneyHelper(A, left + 1, right - 1));
        int rightAmount = A[right] + Math.min(maxMoneyHelper(A, left + 1, right - 1), maxMoneyHelper(A, left, right - 2));

        return Math.max(leftAmount, rightAmount);
    }

// Dynamic programming approach

public static int maxMoneyDP(int[] A) {
        int n = A.length;
        int[][] dp = new int[n][n];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }
        return maxMoneyHelper(A, 0, n - 1, dp);
    }

    private static int maxMoneyHelper(int[] A, int left, int right, int[][] dp) {
        if (left > right) {
            return 0;
        }

        if (dp[left][right] != -1) {
            return dp[left][right];
        }

        int leftAmount = A[left] + Math.min(maxMoneyHelper(A, left + 2, right, dp), maxMoneyHelper(A, left + 1, right - 1, dp));
        int rightAmount = A[right] + Math.min(maxMoneyHelper(A, left + 1, right - 1, dp), maxMoneyHelper(A, left, right - 2, dp));

        dp[left][right] = Math.max(leftAmount, rightAmount);
        return dp[left][right];
    }
}

C++ Code


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Naive approach

int maxMoneyNaive(vector<int>& A) {
    int n = A.size();
    return maxMoneyHelper(A, 0, n - 1);
}

int maxMoneyHelper(vector<int>& A, int left, int right) {
    if (left > right) {
        return 0;
    }

    int leftAmount = A[left] + min(maxMoneyHelper(A, left + 2, right), maxMoneyHelper(A, left + 1, right - 1));
    int rightAmount = A[right] + min(maxMoneyHelper(A, left + 1, right - 1), maxMoneyHelper(A, left, right - 2));

    return max(leftAmount, rightAmount);
}

// Dynamic Programming Approach

int maxMoneyDP(vector<int>& A) {
    int n = A.size();
    vector<vector<int>> dp(n, vector<int>(n, -1));
    return maxMoneyHelper(A, 0, n - 1, dp);
}

int maxMoneyHelper(vector<int>& A, int left, int right, vector<vector<int>>& dp) {
    if (left > right) {
        return 0;
    }

    if (dp[left][right] != -1) {
        return dp[left][right];
    }

    int leftAmount = A[left] + min(maxMoneyHelper(A, left + 2, right, dp), maxMoneyHelper(A, left + 1, right - 1, dp));
    int rightAmount = A[right] + min(maxMoneyHelper(A, left + 1, right - 1, dp), maxMoneyHelper(A, left, right - 2, dp));

    dp[left][right] = max(leftAmount, rightAmount);
    return dp[left][right];
} return dp[target_sum];
}
}

Python Code


**// Naive approach**

def max_money_naive(A):
    n = len(A)
    return max_money_helper(A, 0, n - 1)

def max_money_helper(A, left, right):
    if left > right:
        return 0

    left_amount = A[left] + min(max_money_helper(A, left + 2, right), max_money_helper(A, left + 1, right - 1))
    right_amount = A[right] + min(max_money_helper(A, left + 1, right - 1), max_money_helper(A, left, right - 2))

    return max(left_amount, right_amount)

**# Dynamic Programming Approach**

def max_money_helper(A, left, right, dp):
    if left > right:
        return 0

    if dp[left][right] != -1:
        return dp[left][right]

    left_amount = A[left] + min(max_money_helper(A, left + 2, right, dp), max_money_helper(A, left + 1, right - 1, dp))
    right_amount = A[right] + min(max_money_helper(A, left + 1, right - 1, max_money_helper(A, left, right - 2, dp))

    dp[left][right] = max(left_amount, right_amount)
    return dp[left][right]

Javascript Code

// Naive Approach

function maxMoneyNaive(A) {
    const n = A.length;
    return maxMoneyHelper(A, 0, n - 1);
}

function maxMoneyHelper(A, left, right) {
    if (left > right) {
        return 0;
    }

    const leftAmount = A[left] + Math.min(maxMoneyHelper(A, left + 2, right), maxMoneyHelper(A, left + 1, right - 1));
    const rightAmount = A[right] + Math.min(maxMoneyHelper(A, left + 1, right - 1), maxMoneyHelper(A, left, right - 2));

    return Math.max(leftAmount, rightAmount);
}

// Dynamic Programming Approach

function maxMoneyDP(A) {
    const n = A.length;
    const dp = Array.from({ length: n }, () => Array(n).fill(-1));
    return maxMoneyHelper(A, 0, n - 1, dp);
}

function maxMoneyHelper(A, left, right, dp) {
    if (left > right) {
        return 0;
    }

    if (dp[left][right] !== -1) {
        return dp[left][right];
    }

    const leftAmount = A[left] + Math.min(maxMoneyHelper(A, left + 2, right, dp), maxMoneyHelper(A, left + 1, right - 1, dp));
    const rightAmount = A[right] + Math.min(maxMoneyHelper(A, left + 1, right - 1, dp), maxMoneyHelper(A, left, right - 2, dp));

    dp[left][right] = Math.max(leftAmount, rightAmount);
    return dp[left][right];
}

👉 Time complexity:-

The time complexity of the dynamic programming approach is O(B * m), where B is the target sum and m is the number of coins. This is because we have a nested loop where the outer loop runs for each coin, and the inner loop runs for each target sum from the coin value to the target sum.

In the dynamic programming approach, we fill a 2D memoization table of size n×n , and for each cell, we make constant time computations. Therefore, the time complexity is O(n^2)

👉 Space complexity:-

The space complexity is determined by the memoization table. We use a 2D table of size nxn, resulting in a space complexity of O(n^2).

Leave a Reply