考虑到一个游戏厌倦了白色和红色方块的命令如下：
（开始w w w w w r r w w w r w w w r w r w r w r w r w w w r w w w r w w w w w w r w w完成）
W=白色。
R=红色。
有三个按钮。
绿色按钮：移动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。
我的问题是如何应用动态算法寻找最优解？
最佳答案
您要做的是生成一个包含最小开销和最佳前一步的数组。你从头到尾把它填满，然后从头到尾读最优解。所以像这样：
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个。
如果您对“过冲标记”没意见，那么您必须添加一个特殊的结束节点，并在结束时添加它自己的特殊规则。