将n写成k个数之和的方法数

这两条公式线是一个数学定义,而不是一个编程算法。希望他们能提供足够的信息,让你能找到任何 P(x,y)

由于第一行有效地定义了两种不同的情况,我想重写公式:

(A) P(n, 1) = 1

(B) P(n, n) = 1

(C) P(n + k, k) = P(n, 1) + P(n, 2) + ... + P(n, k)

所以,如果你想把它们应用到 P(6,2) 然后才是 (C) 可以匹配,因为 (A) 仅与以下内容匹配 P(6,1) 和 (B) 像这样的事情 P(6,6) .

的匹配 P(6,2) 反对 P(n+k,k) k 必须是 2 和 n+k 必须是 6 ,给予 n=4 .

然后是 (C) 扩展到 P(4,1) + P(4,2) . 它的第一部分与 (A) ,第二个反对 (C) . 因此,第一部分给出 1 P(6,2) . 等等

如果要实现函数计算 P(x,y) 值,最简单的方法是将定义公式转换为递归计算。

你必须应用公式 :

   P(6, 2) = P(4 + 2, 2) = P(4, 1) + P(4, 2)

现在开始 P(4, 1) 我们有

   P(4, 1) = P(3 + 1, 1) = P(3, 1) = P(2 + 1, 1) = P(2, 1) = P(1 + 1, 1) = P(1, 1) = 1

借助于 就职 我们可以证明 P(N, 1) = 1 N >= 1

对于 P(4, 2) 我们有

   P(4, 2) = P(2 + 2, 2) = P(2, 2) + P(2, 1) = 1 + P(2, 1) = 
           = 1 + P(1 + 1, 1) = 1 + P(1, 1) = 1 + 1 = 2

最后

   P(6, 2) = P(4 + 2, 2) = P(4, 1) + P(4, 2) = 1 + 2 = 3

一般情况下(再次 就职 ) P(2 * N, 2) = N

最简单的 C# 实现(对于某些输入不起作用,例如 P(0, 1)

private static Dictionary<Tuple<int, int>, int> s_Cached = 
  new Dictionary<Tuple<int, int>, int>();

private static int P(int n, int k) {
  if (n == k)
    return 1;

  if (s_Cached.TryGetValue(new Tuple<int, int>(n, k), out var value))
    return value;

  int result = 0;

  for (int i = 1; i <= k; ++i)
    result += P(n - k, i);

  s_Cached.Add(new Tuple<int, int>(n, k), result);

  return result;
}

测验

Console.WriteLine(P(6, 2));