动态规划中的一个证明问题

aimisiyou

A、B两人下一个双人游戏:N个正整数的序列放在一个游戏平台上（例如4 7 2 9 5 2），两人轮流从序列的两端取数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。A、B均按最优策略执行，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。A、B按顺序按最优策略的过程形成一条最优路径。显然，给定的数列若是按规律排列（如递增或递减），那么最优路径总条数仅有一条。

猜想：若数列不是按规律排列，那么最优路径总条数一定是偶数。不知能否证明？

例如数列（4 7 2 9 5 2）的四条最优路径为：
（2，5，9，2，7，4）
（2，5，9，4，7，2）
（2，4，7，5，9，2）
（2，4，7，2，9，5）

aimisiyou

当有n个数时，A可能的取值为2个或1个，留下n-1个数，然后B可能的取值为2个或1个，留下n-2个数，再接着A可能的取值为2个或1个…故总路径条数为1或2^k的形式。
不知这样算不算证明？

王守恩

aimisiyou 发表于 2018-5-19 09:42
当有n个数时，A可能的取值为2个或1个，留下n-1个数，然后B可能的取值为2个或1个，留下n-2个数，再接着A可能 ...

题目是否可以先化简？
1，N个正整数就看作1——N，最优策略好像没有变？
2，只要有先手的最优路径就可以了？
3，先讨论先手占不到便宜的算法？

补充内容 (2018-5-20 09:17):
第1条有问题：N个正整数就看作是从1开始的连续数，最优策略好像没有变？

aimisiyou

王守恩 发表于 2018-5-19 10:19
题目是否可以先化简？
1，N个正整数就看作1——N，最优策略好像没有变？
2，只要有先手的最优路径就可 ...

要是递增或递减就太简单了，先手总是取大的值。

hujunhua

如果N是偶数，先手方有非负策略。

一、先手方首先比较奇数项之和和偶数项之和，如果不相等，比如奇数项之和较大，那么先手方就首取第1项。剩下的序列首尾都是偶数项，后手方只能取到偶数项，然后又剥出一个奇数项，接着被先手方取走，剩下的首尾又都是偶数项。依此下去，先手方就能取到全部奇数项。后手方取到全部偶数项，先手方胜。
二、如果奇数项之和与偶数项之和相等，先手方可简单地依上述方法取到全部奇数项，立于不败。但先手方可以改进一下策略，还有胜机。如果先手方在前面的若干回合中取得了总和较多的数，那么剩下的偶数个数，奇数项之和与偶数项之和就不再相等，先手方可以改变奇偶取向，选择剩下的总和较多的一半从而取胜。
三、在奇数项之和与偶数项之和相等的情况下，先手方可以控制任选奇偶，后手方可以控制先手方的取数顺序，那么问题来了：是否存在一个非常数的序列，后手方可以控制不让先手方在前面的回合中取到较多的和？

hujunhua

{1, 3, 2, 1, 3, 2}这种简单的双重序列（每个数出现2次），先手方无法取胜。所以上楼的问题答案是肯定的。或许我们应该换一种问法。

aimisiyou

hujunhua 发表于 2018-5-20 14:25
如果N是偶数，先手方有非负策略。

一、先手方首先比较奇数项之和和偶数项之和，如果不相等，比如奇数项 ...

先手取胜时的总和和先手取的总和达到最大是一个问题么？

hujunhua

aimisiyou 发表于 2018-5-20 20:09
先手取胜时的总和和先手取的总和达到最大是一个问题么？

“A、B均按最优策略执行，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。”

何谓“当前情况下最大可能的总分”，要看几步？如果只看一步的话，{4, 7, 2,  9, 5, 2}首取不该是4么？

aimisiyou

hujunhua 发表于 2018-5-21 12:06
“A、B均按最优策略执行，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。”

何谓“ ...

哦表述错误了。最优策略应该是整局下来总分达到最大。

aimisiyou

试了几个例子，按最优策略与按奇偶分析策略结果一致。难道两者等价？