java - 将循环内递归的简单递归方法转换为迭代方法

Question

前一段时间，我正在研究一个编程问题 (CCC)。我在过去的比赛中也遇到过类似的问题，所以我决定问一下这个问题。问题基本上是这样的。

给你 n 个人和 p block 馅饼。

n个人站成一排。

你必须在他们中间分配 p block 馅饼。你按顺序走，每个人必须至少收到与他们前面的人一样多的棋子。每个人至少要分到一 block 馅饼，不能有剩余。

您必须返回分配馅饼的可能方式的数量。

我设法创建了以下递归解决方案，但对于以下输入来说它花费的时间太长(超过 5 秒):

120件，20人--> 97132873

250件，130人--> 1844349560

我的解决方案:

import java.io.*;

public class Main
{
  int pieces, people;
  int combinations = 0;

  public void calculate (int person, int piecesLeft, int prev)
  {
    if (person == people)
    {
        if (piecesLeft == 0)
            combinations++;              
    }
    else
    {
        for (int x = prev ; (x * (people - person)) <= piecesLeft ; x++)
        {
            calculate (person + 1, piecesLeft - x, x);
        }
    }
  }


  public static void main (String[] args) throws Exception
  {
    Main m = new Main ();
    BufferedReader in = new BufferedReader (new InputStreamReader (System.in));
    //m.pieces = Integer.parseInt (in.readLine ());
    //m.people = Integer.parseInt (in.readLine ());
    m.pieces=250;
    m.people=130;
    if (m.people == m.pieces)
        System.out.println (1);
    else if (m.people == 1)
        System.out.println (1);
    else
    {
        m.calculate (0, m.pieces, 1);
        System.out.println (m.combinations);
    }
  }
}

我从非官方解决方案中找到了以下 python 解决方案，根据我的理解，它基本上创建了一个已经遇到的值的数组。

visited = []
def pi(n,k,min):
if visited [n][k][min] == 0:       
    if n == k:
        visited[n][k][min] = 1
    elif k == 1:
        visited[n][k][min] = 1
    else:
        t = 0
        for i in range (min, (n / k)+1):
            t = t + pi(n-i, k-1, i)
        visited[n][k][min] = t
return visited[n][k][min]


file = open("j5.10.in", "r")
n = int(file.readline())
k = int(file.readline())

for i in range(n+1):
x = []
for j in range(k+1):
    t = []
    for kk in range(n+1):
        t.append (0)
    x.append(t)
visited.append(x)

print pi(n,k,1)

我想做的是从其中任何一个中得出一个迭代解决方案，但我不确定如何去做。据我了解，可能不会有很大的速度差异，但在更大的情况下，它可以让我避免堆栈溢出。

Answer 1

第二个解决方案是 memoized ... visited 数组记录已经计算过的值。将内存递归转换为(某种)迭代解决方案的技巧是循环遍历较小的案例以填充备忘录数组。您可以丢弃较小情况的结果(无论如何它们都会存储在 memo 数组中)。然后当你最终计算出你想要的那个时，它会立即使用 memo 数组，没有额外的计算。

如果您真的想从头开始构建迭代解决方案，则必须弄清楚需要存储哪些先前案例才能构建下一个案例。例如，要计算阶乘，用一个循环，你只需要在内存中存储一​​个值。在面额为 1、5 和 10 美分的硬币的找零问题中，您只需要保存十个以前的项目来构建下一个。在某些情况下，您需要知道所有以前的值才能构造下一个。知道了，内存结构就清楚了，程序逻辑也就清晰了。