Optimal Strategy Game Pick from Ends of array Dynamic Programming
N pots, each with some number of gold coins, are arranged in a line. You are playing a game against another player. You take turns picking a pot of gold. You may pick a pot from either end of the line, remove the pot, and keep the gold pieces. The player with the most gold at the end wins. Develop a strategy for playing this game.
Optimal Strategy Game Pick from Ends of array Dynamic Programming
Input : { 3, 9, 1, 2 }
Output : 11
package com.omt.learn.algo; class Data { int left = 0; int right = 0; public static Data getData(int l, int r) { Data d = new Data(); d.left = l; d.right = r; return d; } } public class OptimalGameProblem { public static void main(String[] args) { int a[] = { 3, 9, 1, 2 }; System.out.println(getMaxForPlayerOne(a)); } public static int getMaxForPlayerOne(int[] a) { Data[][] matrix = new Data[a.length][a.length]; for (int l = 1; l <= a.length; l++) { for (int i = 0; i < a.length; i++) { int j = i + l - 1; if (j < a.length) { if (l == 1) { matrix[i][j] = Data.getData(a[i], 0); } else { int leftPick = a[i] + matrix[i + 1][j].right; int rightPick = a[j] + matrix[i][j - 1].right; if (leftPick > rightPick) { matrix[i][j] = Data.getData(leftPick, matrix[i + 1][j].left); } else { matrix[i][j] = Data.getData(rightPick, matrix[i][j - 1].left); } } } } } printMatrix(matrix); return matrix[0][a.length - 1].left; } public static void printMatrix(Data[][] matrix) { for (Data[] datas : matrix) { for (int i = 0; i < datas.length; i++) { Data d = datas[i]; if (d == null) { System.out.print("(--,--) "); } else { System.out.print("(" + appendZero(d.left) + "," + appendZero(d.right) + ") "); } } System.out.println(); } } public static String appendZero(int v) { return v < 10 ? "0" + v : v + ""; } }