以大多数k次移动和最高分数查找网格中的路径
我试图解决以下问题：给出N乘M正整数的网格，找到从左上角到右下角的最大分数。 一个路径得分是你在所述路径上收集的所有值的总和（停留在同一个单元格上是可能的转弯）。 另外，路径的长度大多是L 例如：假设我们有以下网格（ N = 5 ， M = 6 ）：
1 1 1 1 1 1
10 10 1 1 1 1
1 10 1 10 10 10
1 10 10 10 1 10
1 1 1 1 1 1
如果L = 10 ，答案应该是83.通过以下路径得到这个结果：
1
10 10
10
10 10 10 1 10
1
并保持在10回合中的一个回合。
如果L = 11 ，答案应该是102.你通过在原始网格中按照10的路径得到这个。
我提出了一个复杂度为O（N ^ 2 * M ^ 2 * L）的算法，但是这太慢了，因为N和M可以达到100，而L可以达到1000.我的算法的基本思想是计算每个元组(i1, j1, i2, j2, k)的答案，其中(i1, j1)是起始单元格， (i2, j2)是目标单元格， k是路径长度。 我从k = 0开始，继续前进到L 你对如何优化这个想法有什么建议吗？ 甚至是对问题的全新认识？
一种可能的方法是针对形式（i，j，k）的每个元组计算长度精确为k的路径的最大得分，该路径从小区（0,0）开始并以（i，j）结束。 让我们把这个值表示为最好的（i，j，k）。
按照惯例，如果没有从（0，0）开始到（i，j）结束的长度为k的路径，我们希望具有最好的（i，j，k）= -infinity。
对于k = 1，有一条长度为1的路径从左上角开始，因此：
对于k> 1，我们可以使用best（*，*，k - 1）的值来计算best（i，j，k）：
最好的（i，j，k）= input_matrix（i，j）+ max（best（a，b，k-1）），其中max取代所有a，b，使得单元格（a，b）是小区的邻居（i，j）。
现在，已经构建出最好的矩阵，可以通过计算找到原始问题的答案：
max（最佳（N-1，M-1，k）），其中max取1和L之间的所有k。
这种方法的复杂性是O （N⋅M⋅L）。
链接地址: http://www.djcxy.com/p/63853.html上一篇: Find path in grid with mostly k moves and maximum score