擅长:python、mysql、java
<h2>我相信你想解决<a href="https://projecteuler.net/problem=15" rel="nofollow noreferrer">this problem</a></h2>
<p>如果是这样,那么您是正确的,它将是明智的解决递归。在</p>
<p>如果您将网格的每个角落想象为一个节点,那么您需要一个递归函数,它只需接受它所在节点的参数{<cd1>}。在函数中,它首先需要检查调用它的位置是否是网格的右下角顶点。如果是,函数会将一个添加到<code>path count</code>(当路径到达这个角时,路径就结束了),然后返回。否则,这个函数只调用另外两个自身(这是递归),一个调用它的<code>right</code>(so<code>y+1</code>),另一个调用它的<code>left</code>(<code>x+1</code>)。另外一个步骤是检查坐标是否在网格中,然后将其作为最下面一行中间的节点调用,例如不应该调用它下面的节点,因为那样会脱离网格。在</p>
<p>现在已经定义了递归函数,现在只需声明一个变量来存储<code>path count</code>。并从坐标(<code>0,0</code>)调用递归函数。在</p>
<p>但是,正如我确信您已经看到的,这个解决方案并没有在合理的时间内完成,所以您有必要使用<code>memoization</code>-通过缓存节点来加速它,这样相同的路径部分不会被计算两次。在</p>
<p>如果像您所做的那样,我们从右下角向上到左上角工作,这也使编码变得更加简单。最后一件事是,如果使用<code>dictionary</code>,那么代码会变得更清晰。在</p>
<p>最后的代码应该类似于:</p>
<pre><code>cache = {}
def pathCounter(x, y):
if x == 0 or y == 0:
return 1
if (x,y) in cache:
return cache[(x,y)]
cache[(x,y)] = pathCounter(x, y-1) + pathCounter(x-1, y)
return cache[(x,y)]
print(pathCounter(2,2))
</code></pre>
<p>这将得到<code>6</code>的预期结果。在</p>
<p>我让你来做<code>20x20</code>网格。希望这有帮助!在</p>