LintCode 476. Stone Game

http://www.lintcode.com/en/problem/stone-game/


Game Theory problems are classified as DP problems.

And this is a classic one. Because there are two players gaming and so many possible moves,

that comes with a huge searching space with a lot of overlaps.

So overlaps must be eliminated by Memoization.

And let's see the 4 Elements of the DP:

1. initialization: (or termination)
dp[i][i] = 0;

2. transfer formula:
dp[i][j] = sum[i][j] + (for all the possible k) min(dp(i, k) + dp(k, j));

3. Result:
dp(0, length - 1);

	public class Solution {
	/*
	* @param A: An integer array
	* @return: An integer
	*/
	public int stoneGame(int[] A) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return 0;
	}
	int len = A.length;
	dp = new int[len][len];
	sum = new int[len][len];
	flag = new boolean[len][len];
	for (int i = 0; i < len; i++) {
	sum[i][i] = A[i];
	for (int j = i + 1; j < len; j++) {
	sum[i][j] = A[j] + sum[i][j - 1];
	}
	}
	// return the final result
	return helper(0, len - 1, A);
	}
	int[][] dp;
	int[][] sum;
	boolean[][] flag;
	int helper(int i, int j, int[] A) {
	if (flag[i][j]) {
	return dp[i][j];
	}
	if (i >= j) {
	return 0;
	}
	flag[i][j] = true;
	int min = Integer.MAX_VALUE;
	for (int k = i; k < j; k++) {
	min = Math.min(min, helper(i, k, A) + helper(k + 1, j, A));
	}
	dp[i][j] = sum[i][j] + min;
	return dp[i][j];
	}
	}

view raw LintCode 476. Stone Game - LintCode.java hosted with ❤ by GitHub