将递归蛮力优化为更加数学/线性的解决方案

Question

我已经编写了这个Haskell程序来解决Eu​​ler 15(它使用一些非常简单的动态编程来运行得更快,所以我实际上可以运行它,但删除你期望它运行的O(2^n).

-- Starting in the top left corner of a 2×2 grid, and only being able to move to
-- the right and down, there are exactly 6 routes to the bottom right corner.
--
-- How many such routes are there through a 20×20 grid?

calcPaths :: Int -> Integer
calcPaths s
 = let  go x y
          | x == 0 || y == 0    = 1
          | x == y              = 2 * go x (y - 1)
          | otherwise           = go (x - 1) y + go x (y - 1)
   in   go s s

我后来才意识到这可以O(n)通过将其转换为方程式并且稍微考虑它来实现,实现它实际上与我上面的解决方案非常相似,除了递归(在我们的硬件上很慢)被表示的数学代替同样的事情(在我们的硬件上速度很快).

是否有一种系统的方法来执行这种优化(生成并证明一个方程以匹配递归)的递归表达式,特别是可以实际"教导"到编译器的一个,所以这种减少是自动完成的？

Answer 1

如果问题可分为较小的子问题，例如，您还可以使用动态规划

F(x,y) = F(x-1,y) + F(x,y-1)

这里 F(x,y) 可分为更小的子问题，因此可以使用 DP

int arr[xmax+1][ymax+1];

//base conditions 

for(int i=0;i<=xmax;i++)
 arr[i][0] = 1

for(int j=0;j<=ymax;j++)
 arr[0][j] = 1;

// main equation

for(int i=1;i<=xmax;i++) {

  for(int j=1;j<=ymax;j++) {

     arr[i][j] = arr[i-1][j] + arr[i][j-1];
  }
} 

正如您提到的，编译器优化 DP 可以用于执行此操作，您只需要在编译器中编写指令，当给出递归解决方案时，检查它是否可分为较小尺寸的子问题（如果是），然后使用 DP 进行简单的 for 循环构建，例如上面但最困难的部分是自动优化它，例如上面的 DP 需要O(xmax*ymax)空间，但可以轻松优化以在O(xmax+ymax)空间中获得解决方案

解算器示例：- http://www.cs.unipr.it/purrs/