recursion - 唯一路径 动态规划

Question

你有一个二维网格。您的移动次数有限。您可以向右、向下、向左和向上。你需要找到逃离网格的方法的数量。所以一个 1 x 2 的网格有 3 个动作，有 9 条独特的路径可以逃离网格（逃避是越界）。

我需要提出一种动态编程方法，到目前为止，我只能考虑您可以采取的不同举措：

1. 你在网格上并且没有移动：继续前进
2. 你出界和出招：1 + 尝试寻找另一条路径
3. 你出界了，没有出招：1+后退一步，另找路径
4. 你在网格上，没有动作：这条路不算数，后退一步，找到另一条路

我想不出一种存储值以避免重新计算的方法，因为您可以从任何时候开始，并且有多个地方可以结束，并且移动次数有限。

标签： recursiondynamic-programmingmemoization