寻找最优解的动态算法
考虑到一个厌倦了白色和红色方块的游戏，顺序如下：
(开始w r r w r w w完成)
W=白色。R=红色。
有3个按钮。绿色按钮:移动5步。黄色按钮:移动3步。蓝色按钮:移动3步。
游戏规则：-如果玩家落在红色方块上，就输了。-第一个完成游戏的玩家获胜。-白色方块上的土地是允许的。
贪心算法：
x = 0
steps = 0
stop = false
while (....)
if a[x+5] is white then
push the green buttton and x= x+5, steps++
if a[x+3] is white then
push the yellow buttton and x= x+3, steps++
if a[x+2] is white then
push the blue buttton and x= x+2, steps++
else stop = true必需:赢得游戏所需的最少步骤。
通过遵循上面的贪婪算法，解将是552225，而最优解是33555。
我的问题是如何应用动态算法来找到最优解？
回答 3
Stack Overflow用户
发布于 2018-11-06 04:08:27
您要做的是生成一个包含最小成本和最佳前一步的数组。你从头到尾把它填满，然后从头到尾阅读最优解。所以就像这样：
min_cost = [infinite for all steps]
arriving_move = [none for all steps]
For each i in 0 to steps-1:
if square[i] = 'r':
pass
else:
for j in 2, 3, 5:
if i <= j:
if min_cost[i-j] + 1 < min_cost[i]:
min_cost[i] = min_cost[i-j] + 1
arriving_move[i] = j
reversed_answer = []
i = steps-1
while arriving_move[i] is not none:
reversed_answer.append(arriving_move[i])
i = i - arriving_move[i]
answer = reversed(reversed_answer)请注意，这将找到一个最优的游戏，其中您直接到达终点。因此，在您的示例中，移动将达到33553。
如果你同意“越界”，你必须在结尾处添加一个特殊的结点，并在结尾处有自己的特殊规则。
Stack Overflow用户
发布于 2018-11-06 04:13:28
Idea:向后思考。假设您在i中。访问此单元的选项有哪些？
// Assume cell[i] = min number of moves to last cell starting from this cell
cell[n] = 0 //finish cell
cell[0..n-1] = ∞
for i = n to 1
cell[i-1] = min(cell[i-1], cell[i]+1) //if cell[i-1] not red
cell[i-3] = min(cell[i-1], cell[i]+1) //if cell[i-3] not red
cell[i-5] = min(cell[i-1], cell[i]+1) //if cell[i-5] not red最后，cell[0]的值显示了完成游戏所需的最少步骤。
Stack Overflow用户
发布于 2018-11-06 05:04:17
要到达终点，您应该首先在以下两个位置中的任何一个上着陆
finish - 5或finish - 3或finish - 2，然后在那里再单击一次按钮即可访问finish。
其递归公式如下：
minSteps(end) = 1 + Math.min( minSteps(end-5), Math.min(minSteps(end-2), minSteps(end-3)) )
您可以使用memoization在(Java)中编写以下代码：
private static int minSteps( int start, int end, String s ) {
if ( end < start ) return Integer.MAX_VALUE;
if ( end == start ) return 0;
if ( s.charAt(end) == 'r' ) {
dp[end] = Integer.MAX_VALUE;
return dp[end];
}
if ( dp[end] != -1 ) return dp[end];
int stepTwo = minSteps( start, end - 2, s );
int stepThree = minSteps( start, end - 3, s);
int stepFive = minSteps( start, end - 5, s );
int min = Math.min( Math.min( stepTwo, stepThree ), stepFive );
if ( min != Integer.MAX_VALUE ) {
dp[end] = 1 + min;
} else {
dp[end] = min;
}
return dp[end];
}对于input：w w w w w w r r w w w w r w r w r w，生成的dp数组将是：
[-1, 2147483647, 1, 1, 2, 1, 2147483647, 2147483647, 2, 3, 2, 3, 2147483647, 3, 2147483647, 3, -1, 4]和答案是4：18 -> 16 -> 11 -> 6 -> 1
然后，您可以通过遵循dp数组从末尾构建您的跳转。
https://stackoverflow.com/questions/53161051
复制相似问题
腾讯云开发者
