埋坑，解答Mayday85和hyf

calatan number



首先回顾问题：
1.n×n的棋盘从左下走到右上，只允许向右和向上，有多少种走法
2.如果不允许越过对角线，那么有多少种走法。

解答：
1.在2n个选择中，选择出n个向上的step，所以C(2n,n)
2.事实上第二问是Catalan数问题的等价问题。

参照我上面的图，从左下走到右上A点，共有C(2n,n)种走法，凡是越过了对角线（那条红线的，就是应该去掉的走法），如果越过了这条线，那么必然要经过斜线b1上面的点，任意取一条经过b1上面点的路径，假设经过的点是c，考虑C到A和B，这2点的情况，显而易见的是A，B关于b1对称。所以，从C到A 的路径数和C到B的完全一样，一一对应。那么连接上从左下点到c点的路径，那么越过对角线的路径的数目等于从左下到B点的路径数，从左下到B点的路径数目用上面的方法，可以知道是C(2n,n-1)

所以我们所求的是c(2n,n)-C(2n,n-1).
当然上面的这种做法比较优美。但是绝对不是catalan number问题的唯一解法，解法太多了，最常用的就是递归归纳，网络上有很多。

Catalan问题极为经典：
等价问题很多，比如给n个顶点，可以组成多少个二叉树，n个数入栈，可能的出栈顺序，n个顶点的凸多边形，可能划分为三角形的组合，可能的方案数目。算是组合数学中的一个小问题而已。

http://en.wikipedia.org/wiki/Catalan_number

我在砖头贴子里提到Catalan数的变种，就是想告诉某些自称可以对逻辑智力问题过目不忘的童鞋一个道理。数学问题不是可以靠强记的，NP问题就那么几种，但是如何证明一个问题等价于已知的np问题，足够你在软件学报发篇文章了。

我一直没告诉你
我觉得 逻辑智力问题 ！= 数学问题
不擅长数学问题 也不喜欢数学问题 更不会过目不忘
那天作题 完全是当天的情境下被逼的……

我喜欢100金币、病狗那样的题
不喜欢微软扔2台xbox那种题

我是这贴的需求之一 给个良好吧

博弈论，对策论都是数学的延伸，不管你是否喜欢，数学都是程序员的基本素质。如果你面对的问题更加不模式化，不是除了sql，处理表单这些一成不变的东西。你会遇到形形色色的问题。如果用比较好的方式解决本身和语言无关。

和我想到的第二个方法一样，
可惜是先受了归纳启发，所以我认为我没有完成这道题。

归纳确实可以解决，我一开始也使用归纳的。不过式子很繁琐，不想写。如果独立想到上面这个方法，已经很强大了，赞一个