|
最近比较忙，先把原题和答案放上来，稍后总结。
此题的目的是想考察一下动态规划的算法，从参赛答案来看除了willin2000 兄外，其他的都是递归算法。
动态规划是一种比较常用的算法，对此类的问题，其效率要比递归高。 若只考虑走一次的情况，则是一个标准的动态规划的过程。
根据走的步数来分阶段
阶段：阶段1，在位置(1,1)，阶段2，位置可能有两个(1,2)，(2,1)，等。其中的规律是阶段k，可能的位置是(x,k+1-x),(k>=x>=1)
状态：每个阶段有若干个状态，如上所述阶段k的状态有: (x,k+1-x),(k>=x>=1)。
决策：在每个位置有可能有两个或一个决策可选择，即向下或向右走（当然不能出界）。
状态转移方程：
位置(x,y)的状态：S(x,y)=min{ s(x-1,y), s(x,y-1) }+格子(x,y)中的数。 现考虑走两次。
题目中是两次分开走的，但我们可以看成两个人同时走。这时依然按照行走的步数来分类。
这样的情况下有一个不同的情况是：可能两个人同时走入同一个格子取数，这时肯定不能取两次数。
两条路线同时进行的动态规划中，状态和决策以及状态转方程移要复杂一些。 两条路线同时进行的动态规划
阶段：按所走的步数来分阶段，从左上角走到右下角，共2n-1个步骤，故共2n-1个阶段。但，有两条线路，故每一阶段的状态都会复杂一些。
状态：有两线路同时走，在某阶段的某状态，要用两个坐标来分别表示两线路的两个点。如：第一阶段，共一个状态：(1,1),(1,1)；第二阶段，(1,2),(1,2);(1,2),(2,1);(2,1),(1,2);(2,1),(2,1)共四个状态。
由于在第k阶段的任何两个点的x,y坐标是有关系的：k+1=x+y。故可只用ｘ坐标来表示一点的坐标，故状态可表示为(x1,x2)，对应的y坐标为：y1=k+1-x1,y2=k+1-x2。
决策：若用0,1分别表示向下或向右走，则每个状态的可能决策有四种：(1,1),(0,0),(1,0),(0,1)。两个数值分别表示两个点的下一步走向。
状态转移方程：
设map(x,y)为方格图，f(k,x1,x2)表示第k个阶段走到(x1,x2)状态的最大和
f(0,1,1)＝map(x1,1+1-x1) 即map(1,1)
f(k,x1,x2)=max{f(k-1,x1',x2')+map(x1,y1)｜x1=x2，f(k-1,x1',x2')+map(x1,y1)＋map(x2,y2)｜x1<>x2} (x1',x2')表示可通过某决策到达(x1,x2)的所有点。 动态规划有点类似递归，通过一个数组来存放每一步的结果，数组后面的值是由前面的值得来的，一般最后一个值就是所要的结果。
[此贴子已经被作者于2007-12-2 15:24:56编辑过] | 
楼主: agstick
沪公网安备 31011702000001号 沪ICP备11019229号-2
发表于 2007-11-19 12:33
发表于 2007-11-20 16:37
楼主
