algorithm - 二维平面上的点与平面原点之间的不同路径数

Question

假设，我在一个二维平面的原点。我想通过精确的 N步到达点（x，y）。

如果我目前在点 (p,q)，那么我可以在之后去点 (p+1,q), (p,q+1), (p-1,q), (p,q-1)一步。

我可以使用多少条不同的路线来做到这一点？请注意：N 最多为 1000 万。

Answer 1

这里的新答案： 在分析计算表之后 - 可以通过一些组合找到路径的数量。

Delphi 代码（注意长算法应该用于 Int64 范围以外的大数）：

function PathCount(x, y, N: Integer): Int64;
var
  t, Diff: Integer;
begin
  x := Abs(x); //exploit symmetry
  y := Abs(y);

  if y > x then begin  //Swap them for simplicity, exploit symmetry again
    t := x;
    x := y;
    y := t;
  end;

  Diff := N - (x + y);
  if (Diff < 0) or Odd(Diff) then
    Exit(0);  //return 0 for unavailable points

  Diff := Diff div 2;
  Result := CombinationCount(N, x + Diff) * CombinationCount(N, Diff);
end;


function CombinationCount(n, k: Integer): Int64;
var
  i: Integer;
begin
  Result := 1;
  if k > n - k then
    k := n - k;
  for i := 1 to k do
    Result := (Result * (n - i + 1)) div i;
end;

---

旧答案（用于演示）

对于合理的 N，可以使用动态规划。制作具有限制的 3d 数组 (-N/2..N/2),(-N/2..N/2),(0..N)。请记住，它的大小是 N^3（10^21 代表 1000 万个点，不切实际）。您可以利用对称性，但缩减因子只是很小的常数（2 或 4）。

递归公式：

P(p, q, K) = P(p-1, q, K-1) + P(p+1, q, K-1) + P(p, q-1, K-1) + P(p, q+1, K-1)

逐层填充数组：第一步使 P(x-1,y0,1) = 1（以及更多 3 个点）等等... 0、1 和 2 步后初始点的邻域：

                  0 0 1 0 0
0 0 0    0 1 0   0 2 0 2 0
0 1 0    1 0 1   1 0 4 0 1
0 0 0    0 1 0   0 2 0 2 0
                  0 0 1 0 0 

6步动画：

完成后，P(0, 0, N) 将包含路径数。

PS可能，有一些组合公式。例如，我们可以在最后一个对角线 (1 2 1, 1 3 3 1, 1 4 6 4 1 ...) 中看到二项式系数 C(N,K)，下一个非零对角线包含 N * C(N, K) 以此类推。