感谢微信平台---一天一道算法题---每天多一点进步-
problem:
12个高矮不同的人 排成两排 每排必须是从矮到高排列 而且第二行比对应的第一排的人高 问排列方式有多少种？
analyse:
据说 这题 是来自于 阿里巴巴的面试题 果然 很有分量 ~~
我反正 胡思乱想了好多 没搞出个有逻辑的思路出来。。。
微信这边 给我们提供了2种方法：
第一种 我再这边不给出介绍了 因为我自己并没有很好地理解它 很麻烦的思维方面的东西...
第二种 是运用卡特兰数
你要是和我一样 以前没有接触过 卡特兰数 正好可以去了解一下了 我准备再以后的随笔会涉及到它 我也要先去学下。。
先给出 卡特兰数的做法：
令h(0) = 1 , h(1) = 1;
h(n) = h(0)*h(n-1)+h(1)*h(n-2)+……+h(n-1)*h(0) (n>=2)
也可以是 h(n) = h(n-1)*(4*n-1)/(n+1) (n>=2)
the answer:
h(6) = 132;
现在看不懂 也没事 毕竟我们还对 卡特兰数没概念嘛~~
today:
你都如何回忆我 带着笑或是很沉默 这些年来有没有人能让你不寂寞