问求数组中最小数路径的递归法

EN

我会这样做，您可以跟踪当前的索引，以及到目前为止，沿着路径的索引的总和(所以求和将不包括我们跳过的数字)。

public static int play(int[] a, int index, int sum){
    if (index>=a.length) return Integer.MAX_VALUE;  //Path went over last index. Invalid Path. 
    sum += a[index];  //Add on to the sum of the index you are currently on
    if (index == a.length-1){
        return sum;  //If we are at last element, return sum of the path traveled
    }else{
        return Math.min(play(a, index+1, sum), play(a, index+2, sum)); //Continue onto path checking both options
    }
}

测试代码：

public static void main(String args[]) {
    int[] a = new int[]{0, 4, 23, 566, 34, 45, 555, 11, 34, 35, 45, 65, 55, 98, 344};
    System.out.println(play(a, 0, 0));
}

输出：591

希望这能有所帮助。

编辑:好的，删除所有的代码，然后在逻辑上考虑这一点。我认为递归(尤其是路径)的方式是，我派遣个别的小人物，在每次递归之后，我将复制那些小人物，以选择不同的路径。让我们在本例中使用较小的数组[0,1,3,4,1]。

我们从一个小男人开始。他从0开始。他有两个选择。第一个选项是转到1，第二个选项是去3。我们需要走这两条路，因为我们不确定前面有什么。这个小个子男人重复自己把一个人送去1，另一个人去3。

现在，走到小路上的小个子1还有另外两个选择。他要么去3，要么去4。走到3路上的小个子男人还有另外两个选择。他可以去4或1。所以他们复制了自己，让小人物们完成所有的选择。我希望这一切在这一点上都有意义。处理小人物复制到不同路径的代码是：play(a, index+1, sum), play(a, index+2, sum))

一个小个子人一旦走到路的尽头会做什么？他必须告诉原来的小家伙这条路有多远。其代码是：if (index == a.length-1){return sum;}

不过，最初的小个子并不在乎这条路。他需要和走另一条路的人比较，看看哪条比较短。这是由Math.Min控制的。只返回两个小个子男人的较短距离。因此，距离越短的小人就会杀死他的克隆人(:p)，因为我们不喜欢这条路。最后，所有的小人物都会互相残杀，只剩下一个小个子站着，这是最短的距离。:)