Offer收割赛25赛后题目直播讲解

2 answer(s)

1

第四题，另一种思路 http://blog.csdn.net/chenbb1989/article/details/77837505

0

C 题 不一定合法括号序列 我的方法是使用组合数 C(2*n, n+k) - C(2*n, n+k+1) 直接求出。 这个公式类似卡特兰数。

  • 可以简单分析一下这个做法吗？

  • 如果是n对括号，卡特兰数是说：不合法的有 C(2*n, n+1) 种。不合法意味这可能是 bad 指数为1, 为2， 为3，。。。为n。即 C (2*n, k+1) 是 bad 指数至少是1的情况个数。用推导卡特兰数的方法，我算出 bad 指数至少为 k 的情况个数是 C(2*n, n+k) 所以答案是 C(2*n, n+k) - C(2*n, n+k+1)。

  • 添加评论
  • ✖reply

write answer 切换为英文 切换为中文

转发分享

▲