OutputError：在给定约束的矩阵中查找最长路径

Question

我的矩阵是：

4 8 7 3 
2 5 9 3 
6 3 2 5 
4 4 1 6

问题（滑雪）：

每一个数字代表该山区域的海拔。在

从网格中的每个区域（即方框），您可以进入北，南，东，西——但前提是您要进入的区域的标高小于等于您所在区域的标高。在

你只能滑雪下山。在

你可以从地图上的任何地方开始，你正在寻找一个起点，这个起点是由你访问的盒子数量来衡量的，这个起点有一条最长的向下路径。在

如果有几条相同长度的路径，你要选择垂直落差最陡的那条，也就是起始高程和终点高程之间最大的差异。在

我的解决方案：

^{pr2}$

问题：

电流输出（距离、压降、路径）：

[1, 0, [4, 2, 8, 7, 3, 4, 2, 5, 2, 3, 2, 1, 7, 3, 2, 5, 2, 3, 2, 1, 9, 3, 5, 2, 3, 2, 1, 7, 3, 2, 1, 6, 3, 2, 1, 2, 4, 3, 2, 1, 2, 1]]

预期产量：

[5,8,[9,5,3,2,1]]

在这个特定的地图上，最长的向下路径是长度=5，下降=8（9-1=8），路径：9-5-3-2-1。在

Answer 1

主要的问题是你不做任何回溯。你不必做任何事情，只是要适当地保持矩阵的概念。相反，对于您访问的每个方块，您只需将所有合法移动附加到一个列表中。在

相反，考虑将当前路径保持为局部变量。对于给定方块中的每一个合法移动，都要进行单独的递归调用以查找更多的移动。每一个都将添加一个合法的移动到本地路径的末尾。在

每次通话结束后，请将找到的最佳路径与保存的路径（目前为止最好的路径）进行比较；保留这两条路径中最好的一条，然后转到下一个合法的移动路径。当您考虑了四个方向中的每一个之后，请返回调用实例的最著名路径。在

在网上和这个网站上有很多回溯的例子；找出一些你觉得可以理解的例子。你可能会在硬币组合递归（找到一组硬币，增加到一定数量）下看，它们不是相同的算法，但上面的回溯思想显示得更清楚。在

这能让你找到解决办法吗？在