import java.util.*;
class GfG {
public static int dp[][] = new int[1002][1002];
public static int getMaxCoins(int[] coins, int start,
int end)
{
if (start > end) {
return 0;
}
if (dp[start][end] != -1) {
return dp[start][end];
}
int option1
= coins[end]
+ Math.min(
getMaxCoins(coins, start + 1, end - 1),
getMaxCoins(coins, start, end - 2));
int option2
= coins[start]
+ Math.min(
getMaxCoins(coins, start + 2, end),
getMaxCoins(coins, start + 1, end - 1));
dp[start][end] = Math.max(option1, option2);
return dp[start][end];
}
public static int maxCoins(int[] coins, int n)
{
for (int i = 0; i < 1001; i++) {
Arrays.fill(dp[i], -1);
}
return getMaxCoins(coins, 0, n - 1);
}
public static void main(String args[])
{
int[] coins = { 8, 15, 3, 7 };
int n = coins.length;
int maxCoins = maxCoins(coins, n);
System.out.println(maxCoins);
}
}
import java.util.*;
class GfG {
public static int dp[][] = new int[1002][1002];
public static int getMaxCoins(int[] coins, int start,
int end)
{
if (start > end) {
return 0;
}
if (dp[start][end] != -1) {
return dp[start][end];
}
int option1
= coins[end]
+ Math.min(
getMaxCoins(coins, start + 1, end - 1),
getMaxCoins(coins, start, end - 2));
int option2
= coins[start]
+ Math.min(
getMaxCoins(coins, start + 2, end),
getMaxCoins(coins, start + 1, end - 1));
dp[start][end] = Math.max(option1, option2);
return dp[start][end];
}
public static int maxCoins(int[] coins, int n)
{
for (int i = 0; i < 1001; i++) {
Arrays.fill(dp[i], -1);
}
return getMaxCoins(coins, 0, n - 1);
}
public static void main(String args[])
{
int[] coins = { 8, 15, 3, 7 };
int n = coins.length;
int maxCoins = maxCoins(coins, n);
System.out.println(maxCoins);
}
}