以最小的能源成本过河

Question

有一座有两条车道的桥，每条车道都有n板，每个板刻一个数字代表通过它所需的能源成本。您最多有k次从一条车道切换到另一条车道的机会。如何选择路径，使能源成本最小化？

以上就是问题的场景。所以把它翻译成代码，我想它的意思是：

There are 2 arrays, for example: 
CASE 1:                                      CASE 2:
            lane A  lane B                                lane A  lane B
 board5       5       4                         board5       2       4
 board4       9       5                         board4       9       5
 board3       3       4                         board3       3       4
 board2       5       1                         board2       5       1
 board1       1       3                         board1       1       3

在这个例子中，n=5，让我们假设k= 2，这意味着我们最多可以换2次车道。

SO:
The best path should be:
CASE 1:                                      CASE 2:
            lane A  lane B                                lane A  lane B
 board5               4                         board5       2       
 board4               5                         board4               5
 board3               4                         board3               4
 board2               1                         board2               1
 board1       1                                 board1       1       

请注意，在上述情况下，我从A车道开始，因为这是一个更好的答案，但是我们可以从B车道开始，就好像我们可以找到更好的路径一样！

当n，k是任何其他数时，如何选择最佳路径？在这个问题中，车道的数目总是2条，但如果有3条或更多的车道怎么办？

编辑1:我编写了一个方法来获取所有可能的路径，如下所示：

  static ArrayList<String> pathList = new ArrayList<String>();
  static int[][] arrayTree;  //store 2 arrays as one 2-demension array

  public static void findNext(int nextLevel, String path){
        if(nextLevel > arrayTree.length - 1){
            pathList.add(path);
            return;
        }
        for (int i = 0; i < arrayTree[nextLevel].length; i++) {
            if(i == 1 && path.length() != 0){
                path = path.substring(0, path.length() - 2);
            }
            path += arrayTree[nextLevel][i] + " ";
            findNext(nextLevel + 1, path);
        }
    }

下一步是找到所有不超过k次切换的路径，并找到一个代价最小的能量。

虽然这是一个解决问题的方法，但背后的想法是列举所有的可能性，然后进行计算。

但是，必须有更方便的方法，可以使用一些数据结构或算法或动态规划(用于决策过程)知识。

如果对这个问题有其他想法，请告诉我.非常感谢!

Answer 1

据我所见，您可能需要一个算法来计算所有可能的路径，同时考虑到开关的最大值。我想说的是，你应该在没有开关限制的情况下尝试这样做，试着获得所有可能的组合：

A-B，A-B-B，A-B-B，B-A-B-B，B-B等等。

如果你有一条以上的车道，你是否可以选择其他车道，或者仅仅是当前车道旁边的车道？这是你必须考虑的事情。

总之:从小开始，把你的工作分成更可实现的小任务。试着在一张纸上设计你的海藻，先画一些图表，然后再开始编写代码，而不清楚你要做什么。流程图在这里应该是有帮助的。

我希望你能发现我的建议有帮助。PS:这个周末我会自己解决这个问题。