Problem statement: Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row,removes it
from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.
Note: The opponent is as clever as the user.
Let us understand the problem with few examples:
1.5, 3, 7, 10 : The user collects maximum value as 15(10 + 5)
2.8, 15, 3, 7 : The user collects maximum value as 22(7 + 15)
Does choosing the best at each move give an optimal solution?
No. In the second example, this is how the game can finish:
1.
…….User chooses 8.
…….Opponent chooses 15.
…….User chooses 7.
…….Opponent chooses 3.
Total value collected by user is 15(8 + 7)
2.
…….User chooses 7.
…….Opponent chooses 8.
…….User chooses 15.
…….Opponent chooses 3.
Total value collected by user is 22(7 + 15)
So if the user follows the second game state, maximum value can be collected although the first move is not the best.
There are two choices:
1.The user chooses the ith coin with value Vi: The opponent either chooses (i+1)th coin or jth coin. The opponent intends to choose the coin which leaves the user with minimum value.
i.e. The user can collect the value Vi + min(F(i+2, j), F(i+1, j-1) )
2.The user chooses the jth coin with value Vj: The opponent either chooses ith coin or (j-1)th coin. The opponent intends to choose the coin which leaves the user with minimum value.
i.e. The user can collect the value Vj + min(F(i+1, j-1), F(i, j-2) )
Following is recursive solution that is based on above two choices. We take the maximum of two choices.
F(i, j) represents the maximum value the user can collect from
i'th coin to j'th coin.
F(i, j) = Max(Vi + min(F(i+2, j), F(i+1, j-1) ),
Vj + min(F(i+1, j-1), F(i, j-2) ))
Base Cases
F(i, j) = Vi If j == i
F(i, j) = max(Vi, Vj) If j == i+1
Why Dynamic Programming?
The above relation exhibits overlapping sub-problems. In the above relation, F(i+1, j-1) is calculated twice.
很有意思的博弈问题,重要的一点是贪心法在这里是不行的,前面已经举了反证。
另外很重要的一点是对求dp[0][n]而不是dp[m][m]的问题,如何写for循环。文章里说要从对角线开始向右上角递推。
比如:
The below table represents the stored values for the string abcde.
a b c d e
----------
0 1 2 3 4
0 0 1 2 3
0 0 0 1 2
0 0 0 0 1
0 0 0 0 0
How to fill the table?
The table should be filled in diagonal fashion. For the string abcde, 0….4, the following should be order in which the table is filled:
Gap = 1:
(0, 1) (1, 2) (2, 3) (3, 4)
Gap = 2:
(0, 2) (1, 3) (2, 4)
Gap = 3:
(0, 3) (1, 4)
Gap = 4:
(0, 4)
可以用以下代码得到:
用一个gap变量作为l和h之间的距离,然后l和h一起前进,直到h碰到边界n,因为l在左上方,h在右下方,所以肯定h先碰到右边界!
// Fill the table
for (gap = 1; gap < n; ++gap)
for (l = 0, h = gap; h < n; ++l, ++h)
table[l][h] = (str[l] == str[h])? table[l+1][h-1] :
(min(table[l][h-1], table[l+1][h]) + 1);
package DP;
public class OptimalGameStrategy {
public static void main(String[] args) {
int[] A = {8, 15, 3, 7};
int[] B = {2, 2, 2, 2};
int[] C = {20, 30, 2, 2, 2, 10};
System.out.println(optimalStrategyOfGameRec(A, 0, A.length-1));
System.out.println(optimalStrategyOfGame(A, A.length));
System.out.println(optimalStrategyOfGameRec(B, 0, B.length-1));
System.out.println(optimalStrategyOfGame(B, B.length));
System.out.println(optimalStrategyOfGameRec(C, 0, C.length-1));
System.out.println(optimalStrategyOfGame(C, C.length));
}
public static int optimalStrategyOfGameRec(int[] A, int begin, int end){
if(begin == end){ // 只剩下一枚硬币时,只能取那枚
return A[begin];
}
if(begin+1 == end){ // 只剩下两枚时,取大的那枚
return Math.max(A[begin], A[end]);
}
// 如果我去开头那枚,因为对手会拿较大那枚,所以留下的是较小的选择,看图
int a = A[begin] + Math.min(optimalStrategyOfGameRec(A, begin+2, end),
optimalStrategyOfGameRec(A, begin+1, end-1));
// 如果我去拿结尾那枚,同理
int b = A[end] + Math.min(optimalStrategyOfGameRec(A, begin+1, end-1),
optimalStrategyOfGameRec(A, begin, end-2));
return Math.max(a, b); // 做最合算的选择
}
// Returns optimal value possible that a player can collect from
// an array of coins of size n. Note than n must be even
public static int optimalStrategyOfGame(int[] A, int n){
int[][] dp = new int[n][n]; //dp[begin][end]保存从序号为begin到end的coin序列能取得的最大值
// Fill table using above recursive formula. Note that the table
// is filled in diagonal fashion (similar to http://goo.gl/PQqoS),
// from diagonal elements to table[0][n-1] which is the result.
for(int gap=0; gap<n; gap++){
int begin=0, end=gap;
while(end < n){
// 检测条件为右上角
int x = begin+2<=end ? dp[begin+2][end] : 0;
int y = begin+1<=end-1 ? dp[begin+1][end-1] : 0;
int z = begin<end-2 ? dp[begin][end-2] : 0;
dp[begin][end] = Math.max(A[begin]+Math.min(x, y),
A[end]+Math.min(y, z));
begin++;
end++;
}
}
return dp[0][n-1];
}
}
http://www.geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game/
http://www.geeksforgeeks.org/dynamic-programming-set-28-minimum-insertions-to-form-a-palindrome/
分享到:
相关推荐
有一类试题,每相邻两项数之间的变化有一定的规律性,我们可将这种规律归纳成如下简捷的递推关系式:F(n)=G(F(n-1)) 这就在数的序列中,建立起后项和前项之间的关系。然后从初始条件(或最终结果)入手,一步步地按...
编程求所有的n位数中,有几个数有偶数个数字是3, (输入格式):输入n (输出格式):输出方案对12345取模的值
dp入门 数字三角形 人人为我型 递推式 专门为初学dp算法的新手准备
论文研究- 经济增长模型的递推规划方法与最优平衡问题.pdf, 递推规划是复杂经济系统的分解途径,又是一种不同模型组合与连接的方法,近几年在理论研究和实际应用中发展很快。利用递推规划方法建立的我国宏观经济模型,...
例如汉诺塔问题的时间复杂度递推 形式为 T (n)=2T (n−1)+1 (n≥1) ,可以解出封闭形式为 T (n)=2 n −1 (设初始状态 T (0)=0 )。 因为递推式求解的重要性,许多算法书籍对其有专门介绍。Donald Knuth在Concrete ...
将有双亲域的二叉链表进行中序遍历的递推式算法
十种常见的滤波算法用LabVIEW来实现,一维数组输入输出接口已配置好,程序框图有对每种滤波算法进行说明。可直接用枚举变量选择对应滤波方法,分别是: 无滤波 限幅滤波法 中位值滤波法 算术平均滤波法 递推平均滤波...
广义系统ARMA最优递推状态估值器rar,广义系统 广义ARMA状态估值器,广义Wiener状态滤波器 现代时间序列分析方法
1.动态规划、贝尔曼方程、最优值函数、值与策略迭代、最短路径、马尔可夫决策过程。2. 哈密顿-雅可比-贝尔曼方程,近似方法,nite和nite hori- zon公式,随机微积分基础。3.庞特利亚金的极大原理,ODE和梯度下降法,...
递推问题:递推与递归解法 递推问题的一般步骤: 一. 判断是否属于递推问题:这个没有可套用的公式,凭经验,具体问题具体考虑 如果把问题的规模缩小,得到的小问题与原问题在结构上性质上相同或相似,并且子问题与...
递推和DP是有区别的。特此献上雪藏的10道递归题,有多有用方法!希望您有巨大的收获!
单路或者n路AD读取,m次递推中位值平均一阶滤波,n、m值可设置。
递推最小二乘法matlab程序
包括0-1背包、无限背包、有限背包、有价值背包、小数背包(贪心即可)等,是极为经典的模型,其转化与优化也是很重要的。 2、最长非降子序列模型 改版:渡河问题、合唱队型等 3、最大子段和模型 改版:K大子段和、...
关于几种递推
递推最小二乘算法递推最小二乘算法递推最小二乘算法递推最小二乘算法递推最小二乘算法递推最小二乘算法
《算法与数据结构》—递推方程及算法分析
把队列中的N个数据进行算术平均运算,就可获得新的滤波结果 N值的选取:流量,N=12;压力:N=4;液面,N=4~12;温度,N=1~4 B、优点: 对周期性干扰有良好的抑制作用,平滑度高 适用于高频振荡的系统 C、缺点...
《递推数列与数列不等式》作者林炳华: 出版年:1992年
基于MATLAB极大似然递推辩识算法的程序,辩识对象为二阶系统。%信号u(k)为M序列 clc L=1000 y1=1;y2=1;y3=1;y4=0; for k=1:L; x1=xor(y3,y4); %同为0或同为1,取0;否则取1 x2=y1 x3=y2 x4=y3 y(k)=y4 if y(k)...