arrays - 整数数组中的路径数

Question

有一个整数数组，例如。

{3,1,2,7,5,6}

可以一次通过数组向前移动每个元素，也可以根据该索引处的值跳过几个元素。例如，一个人可以从 3 到 1 或 3 到 7，然后一个人可以从 1 到 2 或 1 到 2(这里不能跳跃)，然后一个人可以从 2 到 7 或 2 到 5，然后一个人可以去7 到 5 只有 7 的索引是 3 并且将 7 添加到 3 = 10 并且没有第十个元素。

我只需要计算从起始索引到达数组末尾的可能路径数。

我只能递归地、天真地做它，它在指数时间内运行。

有人请帮助。

Answer 1

我的建议:使用动态规划。

如果这个关键字就足够了，并且您想挑战自己找到可能的解决方案，请不要继续阅读!

这里是示例输入 {3,1,2,7,5,6} 上可能的 DP 算法。针对一般问题进行调整将是您的工作。

创建数组 sol，长度为 6，其中只有零。该数组将保存路数。

sol[5] = 1;
for (i = 4; i>=0;i--) {
     sol[i] = sol[i+1];
     if (i+input[i] < 6 && input[i] != 1)
         sol[i] += sol[i+input[i]];             
}

return sol[0];

运行时间 O(n)

至于评论中提示的有向图解决方案:

数组中的每个单元格代表一个节点。使从每个节点到节点可访问的有向边。基本上，您只需查看节点上的出度(因为没有定向循环)就可以更轻松地计算方法的数量，但是实际编程需要很多样板。

调整递归解法

另一个解决方案是修剪。这基本上等同于 DP 算法。指数时间来自这样一个事实，即您多次计算值。例如函数是 recfunc(index)。初始调用recFunc(0)调用recFunc(1)和recFunc(3)等。但是recFunc(3)必然会在某个时候再次被调用，从而导致重复的递归计算。要修剪它，您需要添加一个 Map 来保存所有已计算的值。如果您调用 recFunc(x)，您会在 map 中查找 x 是否已计算。如果是，则返回存储的值。如果不是，则计算、存储并返回。这样您也可以获得 O(n)。