Snap 面经题目:coins

0002505492

题目:

题目:A跟B在play game,从int[]里拿数字
A:拿第一个/最后一个,都有可能
B:greedy,总拿第一个/最后一个中最大的

A先开始,然后B,轮流,直到拿完
求A拿到的最大

举个例子:
{3, 7, 2, 1}
A: {3, 1} — 4
B: {7, 2} — 9

A: {1, 7} — 8
B: {3, 2} — 5
答案是8。

使用DP。

代码:

public class Solution {
	public static void main(String[] args)
	{
		int[] input = {3, 7, 2, 1};
		System.out.println(coin(input));
	}

	private static int coin(int[] input) {
		// TODO Auto-generated method stub
		if(input == null || input.length == 0) return 0;
		int len = input.length;
		int[][] dp = new int[len][len];
		for(int i = 0; i < len; i++) dp[i][i] = input[i];
		for(int i = 0; i < len - 1; i++) dp[i][i + 1] = Math.max(input[i], input[i + 1]);
		for(int i = 2; i < len; i++)
		{
			for(int j = 0; j + i < len; j++)
			{
				int ch1 = input[j] + (input[j + 1] > input[i + j] ? dp[j + 2][i + j] : dp[j + 1][i + j - 1]);
				int ch2 = input[i + j] + (input[j] > input[i + j - 1] ? dp[j + 1][i + j - 1] : dp[j][i + j - 2]);
				dp[j][i + j] = Math.max(ch1, ch2);
			}
		}
		return dp[0][len - 1];
	}
}

输出:

8

480total visits,1visits today