经过6步后,肯定处于M1中编号为6的位置。共有3个编号为6的,分别对应M2中的2 3 4。假设第1次经过6步走到了M2中的2,第2次经过6步走到了M2中的4,DP[s,i,j] 则对应 DP[6,2,4]。由于s = 2n - 2,0 <= i<= <= j <= n,所以这个DP共有O(n^3)个状态。
再来分析一下状态转移,以DP[6,2,3]为例(
就是上面M1中加粗的部分),可以到达DP[6,2,3]的状态包括DP[5,1,2],DP[5,1,3],DP[5,2,2],DP[5,2,3],加粗表示位置DP[5,1,2] DP[5,1,3] DP[5,2,2] DP[5,2,3] (
加红表示要达到的状态DP[6,2,3])
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
1 2 3 4
5 1 2 3 4
5 1 2 3 4 5 1 2 3 4 5
2 3 4
5
6 2 3 4 5
6 2 3 4
5
6 2 3 4
5
6
3 4 5
6 7 3 4
5
6 7 3 4 5
6 7 3 4
5
6 7
4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8
因此,
DP[6,2,3] = Max(DP[5,1,2] ,DP[5,1,3],DP[5,2,2],DP[5,2,3]) + 6,2和6,3格子中对应的数值 (式一)
2、上面(式一)所示的这个递推看起来没有涉及:“如果两次经过同一个格子,那么该数只加一次的这个条件”,讨论这个条件需要换一个例子,以DP[6,2,2]为例。
DP[6,2,2]可以由DP[5,1,1],DP[5,1,2],DP[5,2,2]到达,但由于i = j,也就是2次走到同一个格子,那么数值只能加1次。
所以
当i = j时,DP[6,2,2] = Max(DP[5,1,1],DP[5,1,2],DP[5,2,2]) + 6,2格子中对应的数值
(式二)
3、故,综合上述的(式一),(式二)最后的递推式就是
if(i != j)
DP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j - 1], DP[s - 1, i, j]) + W[s,i] + W[s,j]
else
DP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j]) + W[s,i]
其中W[s,i]表示经过s步后,处于i位置,位置i对应的方格中的数字。
复杂度分析:状态转移最多需要统计4个变量的情况,看做是O(1)的。共有O(n^3)个状态,所以总的时间复杂度是O(n^3)的。空间上可以利用滚动数组优化,由于每一步的递推只跟上1步的情况有关,因此可以循环利用数组,将空间复杂度降为O(n^2)。
OK,上述这个方法可能不算最优解法,但相对比较容易想一些。希望大家能够提供更好的想法,也欢迎大家补充程序。链接:
http://www.51nod.com/answer/index.html#!answerId=598。