[topcoder]BadNeighbors

http://community.topcoder.com/stat?c=problem_statement&pm=2402&rd=5009

动态规划题。对于圈状的题目有了点感觉。

题目描述:n个数围成一个圆圈，求最大的子集和使得每一个数都不和其他任何数是相邻的。
f[i][0]表示2...i这些数能得到的最大和，f[i][1]表示 1....i-1这些数能得到的最大和。
f[i][0] 和 f[i-1][0] , f[i-2][0]+A[i]有关系, f[i][1] 和 f[i-1][1], f[i-2][0]+A[i]有关系。
计算子问题的顺序:i form 0 to n-1.

public class BadNeighbors {
	public int maxDonations(int[] donations) {
		int len = donations.length;
		if (len == 0) return 0;
		if (len == 1) return donations[0];
		if (len == 2) return Math.max(donations[0], donations[1]);
		
		int[][] matrix = new int[len][2];
		// len >= 3
		// [i][0] means max from 0..i-1
		// [i][1] means max from 1..i
		matrix[1][0] = donations[0];
		matrix[1][1] = donations[1];
		matrix[2][0] = Math.max(donations[0], donations[1]);
		matrix[2][1] = Math.max(donations[1], donations[2]);
		
		for (int i = 3; i < donations.length; i++) {
			matrix[i][0] = Math.max(matrix[i-1][0], matrix[i-2][0] + donations[i-1]);
			matrix[i][1] = Math.max(matrix[i-1][1], matrix[i-2][1] + donations[i]);
		}
		
		return Math.max(matrix[len-1][0], matrix[len-1][1]);
	}
}