关于移动棋子的一个算法问题,请帮帮忙,急。。。

时间:2021-02-22 20:44:37
假设有一张n*n个方格的棋盘以及一个棋子,必须根据以下的规则把棋子从棋盘的底边移动到棋盘的顶边,在每一步你可以把棋子移动到三个方格中的一个:
1、正上方的方格。
2、左上方的方格(只能当这个棋子不在最左列的时候)
3、右上方的方格(只能当这个棋子不在最右列的时候)
每次从方格x移动到方格y,会得到p(x,y)块钱。已知所有(x,y)的p(x,y),只要从x到y的移动是合法的。不要假设p(x,y)是正值。
请给出一个计算移动方式集合的算法,把棋子从棋盘底边的某个地方移动到棋盘顶边的某个地方,同时收集尽可能多的钱。你的算法可以*选择底边的任意方格作为起始点,顶边上的任意方格作为目的点,来最大化一路上收集到的钱数。你的算法的执行时间是多少?

12 个解决方案

#1


其实就是个A*寻路算法。

#2


好像是DP,等会儿再仔细想想

#3


DP,Money[x][y] = max{Money[x-1][y-1], Money[x][y-1], Money[x+1][y-1]} + p(x,y)
复杂度为O(n^2),到下限了,因为至少要遍历所有格点才能得出最优解

#4


如果棋盘很大的话我觉得还可以加一个简单的启发函数剪枝,即如果与目标相差行数> 相差列数,此时可剪

引用 3 楼 peacefulby 的回复:
DP,Money[x][y] = max{Money[x-1][y-1], Money[x][y-1], Money[x+1][y-1]} + p(x,y)
复杂度为O(n^2),到下限了,因为至少要遍历所有格点才能得出最优解

#5


应该是DP吧...好象题目的意思是找出一条路径,使得吃到的金币数最大吧?

#6


该回复于2010-01-19 17:27:49被版主删除

#7


最简单的方法是遍历吧,不过这样比较慢。可在每个方格记录当前点到底边的最大值a,和到顶边的最大值b,当下次再经过这个点时就可以通过比较停止遍历了。当当前值比a小是就停止,比a大时就直接加上b就得出新的最大值。要记录最优路径的话适当增加一个数组就行了吧。这样时间复杂度应该可以算做O(n)吧,不太确定,呵呵。

#8


时间复杂度不大会算,不过感觉应该不用到O(n^2)吧。

#9


又想了想,貌似每个格最少都要两次哦,O(N^2)?!高手指点下!

#10


肯定是用DP了,如果效率的话我感觉用DP中的自上而下的备忘录法可能更高一些,因为好些子问题不需要计算

#11


递归遍历。一路记下已收集的钱数。

#12


..

#1


其实就是个A*寻路算法。

#2


好像是DP,等会儿再仔细想想

#3


DP,Money[x][y] = max{Money[x-1][y-1], Money[x][y-1], Money[x+1][y-1]} + p(x,y)
复杂度为O(n^2),到下限了,因为至少要遍历所有格点才能得出最优解

#4


如果棋盘很大的话我觉得还可以加一个简单的启发函数剪枝,即如果与目标相差行数> 相差列数,此时可剪

引用 3 楼 peacefulby 的回复:
DP,Money[x][y] = max{Money[x-1][y-1], Money[x][y-1], Money[x+1][y-1]} + p(x,y)
复杂度为O(n^2),到下限了,因为至少要遍历所有格点才能得出最优解

#5


应该是DP吧...好象题目的意思是找出一条路径,使得吃到的金币数最大吧?

#6


该回复于2010-01-19 17:27:49被版主删除

#7


最简单的方法是遍历吧,不过这样比较慢。可在每个方格记录当前点到底边的最大值a,和到顶边的最大值b,当下次再经过这个点时就可以通过比较停止遍历了。当当前值比a小是就停止,比a大时就直接加上b就得出新的最大值。要记录最优路径的话适当增加一个数组就行了吧。这样时间复杂度应该可以算做O(n)吧,不太确定,呵呵。

#8


时间复杂度不大会算,不过感觉应该不用到O(n^2)吧。

#9


又想了想,貌似每个格最少都要两次哦,O(N^2)?!高手指点下!

#10


肯定是用DP了,如果效率的话我感觉用DP中的自上而下的备忘录法可能更高一些,因为好些子问题不需要计算

#11


递归遍历。一路记下已收集的钱数。

#12


..