algorithm - 如何找出对 nCr 函数的调用次数

Question

下列递​​归方程的解是什么？

T(n, 0) = 1,
T(n, n) = 1,
T(n, r) = T(n-1, r-1) + T(n-1, r) + 1

我在尝试找出对函数 nCr 的调用次数时得到了这个，在以下 nCr 的定义中

int nCr ( int n, int r ) {
  if( n == r || r == 0 ) 
    return 0;
  return nCr( n-1, r-1 ) + nCr( n-1, r );
}

这个递归方程是否适合这个目的？

Answer 1

我认为你的递归方程是完全正确的(你定义的函数确实总是返回 0，但它与调用次数无关)。

为了解决它，你应该看到它非常接近 Pascal's triangle 后面的递归, 所以 T(n,r) 的值应该与 binomial coefficient 有关C(n,r)。

如果你试着写下这个新三角形的前几行，你会得到:

1
1 1
1 3 1
1 5 5 1
1 7 11 7 1
1 9 19 19 9 1
1 11 29 39 29 11 1 
...

由此您可以使用 OEIS ，或者自己计算出 T(n,r) = 2 * C(n,r) - 1。

然后您可以使用归纳法证明它:如果 r = 0 或 r = n，则关系为真，否则

T(n,r) = T(n-1,r) + T(n-1,r-1) + 1
       = (2 * C(n-1,r) - 1) + (2 * C(n-1,r-1) - 1) + 1
       = 2 * (C(n-1,r) + C(n-1,r-1)) - 1
       = 2 * C(n,r) - 1

希望这对您有所帮助。