Как решить задачу?

Question

[Hello World]

Есть задача:

текст

Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали даже. Что ж, расскажем о новой игре. На доске написана последовательность n целых чисел. Играют двое. На очередном ходе игрок выбирает число с правого или с левого края последовательности, затем это число стирается и последовательность становится на одно число меньше, а ход переходит к противнику. Выигрывает тот, кто наберет в сумме больше. Написать программу, определяющую победителя в конкретной игре, при условии, что игроки будут играть оптимально.
INPUT.TXT
В первой строке входного файла INPUT.TXT записано целое число n (0 < n < 100). Во второй строке через пробел заданы n натуральных чисел, не превосходящих 1000.
OUTPUT.TXT
В единственную строку выходного файла OUTPUT.TXT нужно вывести 1, если победит первый игрок, 2 – если победит второй игрок и 0 – в случае ничьей.

источник

Я написал программу, которая определяет, как мне кажется, наилучший ход на отрезке i..j
Первый игрок пытается увеличить результат, а второй - уменьшить. Я думаю, что это наилушая стратегия.
Но тогда, какой писать ответ? Как понять, что это АБСОЛЮТНО наилучшая стратегия?

Код

for (int j = N-1; j>=0; j--){
		for (int i = 0; i < N; i++){
			if (flag){
				flag = !flag;
				i++;
			}
			sign = ((j+i)%2==0) ? 1:-1;
			if (i < 1){
				dp[j][i] = dp[j+1][i] + sign*arr[j+1];
			}
			else if (j+1 >= N){
				dp[j][i] = dp[j][i-1] + sign*arr[i-1];
			}
			else {
				if (sign == 1){
					dp[j][i] = MAX(dp[j][i-1]+arr[i-1], dp[j+1][i]+arr[j+1]);
				} else {
					dp[j][i] = MIN(dp[j][i-1]-arr[i-1], dp[j+1][i]-arr[j+1]);
				}
			}
			if (i == j)
				dp[j][i] = dp[j][i] - sign*arr[i];
		}
	}

Comments

[Roman]

в №1 3254

#1 -> 4
#2 -> 5
#1 -> 3
#2 -> 2

4 + 3 == 7
5 + 2 == 7

7 == 7

почему победил #1 ?

upd:
понятно

[Hello World]

Roman, потому что 3+5 = 8, 2+4 = 6. У первого игрока больше очков, чем у второго.
А тут уже вопрос о том, почему это лучшая стратегия.

[Roman]

Hello World, источник не укажу, вы же сами хотите решить?

Картинка

Answer 1

[Griboks]

Проверьте все возможные ходы. Выберете те, которые дают наибольшее количество очков за наименьшее количество ходов. Это и есть оптимальная стратегия по определению.

Comments

[Hello World]

а что со вторым игроклм? ему нужно минимизировать счет

[Griboks]

Hello World, второй игрок является переменной - параметром оптимизации.