【原创】如果Dota里的Kael不仅仅能控制冰火雷，还能控制河蟹、囧、萌……等等n个元素的话，他能有几个技能？
EDIT：其实就是n个球，插n-1个板，板可以相邻…… 以下都是废话了……
?
恩 我承认标题党了
这个问题是昨天晚上找Monster.Q和Jay-ZW吃饭的时候，他们再研究的一个问题。仅仅3个元素的话，数一下就可以了，10个。但是元素一多肯定没法数了，也没法说数一下能控制n个元素的情况。
一开始，我们3个人都往排列组合上想了，各种思路总觉得都不靠谱。
Jay-ZW给出了一个n=3时的解：
3个盒子，3个球。 3种情况:
一个盒子里一个球(1+1+1)： C(3,3) = 1 种
一个盒子两个，另外一个盒子一个(2+1)： C(3,1) * C(2,1) = 6 种
一个盒子里放3个(3)： C(3,1) = 3 种
一共10种
很明显，这种方法在n稍微增大的时候，就会让人吐血了 比如5个的时候就要考虑这几种情况
5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1
这个没法让人接受。
==========糗百风格的昏割线0x01==========
想起来当时用来数n=3情况的时候用的一个小技巧：
Q W E
Q W E
Q W E
这样从上往下画线，但是只能向下和向右拐，比如这样
Q W E
Q W E
Q W E
或者这样
Q W E
Q W E
Q W E
==========糗百风格的昏割线0x02==========
我们定义一个函数f(x, y)，f(x, y)的值代表Kael可以控制x种元素，在同时拿出y种元素的情况下，总共的技能数。真实的Kael的话就是f(3,3)=10。
(1) 首先考察一下，x = 1的情况
??? 呃 很明显，只有一种元素可以控制，那就只能拿出一种技能了。。
??? 所以f(1, y) = 1
??? 比如f(1,3) 对应着
??? Q
??? Q
??? Q
??? 即只有QQQ一种
(2) 再考虑一下， y = 1的情况
??? 恩 x种元素，拿出一个， 那就是x个技能了
??? 即f(x, 1) = x
??? 比如
??? Q W E
??? 对应着Q、W、E三种
(3) 恩 正题了
??? 观察楼下是个8x8的矩阵，我们要算出来f(8,8)来。
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? 总不能不选把，好，我们从先选一个，Q吧！
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? 选好了，第二行再选什么？ 等等，如果我们观察一下，就会发现，8x8在第一行选Q的情况下，其实与8x7矩阵的所有情况数量相等，因为8x7的每一种情况头上添个Q就是这种情况了。
??? 同理，如果我第一行选W，情况数与7x7的全部情况数是相等的！
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? Q W E R T Y U I
??? 所以，当我取完第一行的Q、W、E、R……的时候，把他们都加起来，就是8x8矩阵的所有情况！
??? 所以f(8,8) = f(8,7)+f(7,7)+ ... + f(1,7)
推广到x和y，得到：
f(x,y) = f(x, y-1) + f(x-1, y-1) + ... + f(1, y-1)
加上(1)、(2)推出的结论，得出：
{
??? f(x, y) = Sum(f(i, y-1), i = 1 to x)
??? f(x, 1) = x
??? f(1, y) = 1
}
==========糗百风格的昏割线0x03==========
写出程序来，也不是特别复杂，附赠C源代码：
#include <stdio.h>
#include <stdlib.h>
int cache[100][100]; // 偷懒，n别过99就不会出错。 其实n到了一定大小就会溢出f(n,n)就会溢出了
int f(int x, int y)
{
??? int i, sum;
??? if(cache[x][y]) return cache[x][y]; // 计算过则直接返回结果
??? if(y == 1) return x;
??? if(x == 1) return 1;
??? for(i=1, sum=0; i <= x; i++) {
??????? sum += f(i, y-1);
??? }
??? return cache[x][y] = sum;
}
int main()
{
??? int n;
?
??? memset(cache, 0, sizeof(cache));
??? scanf("%d", &n);
??? printf("%d\n", f(n, n));
??? return 0;
}
==========糗百风格的昏割线0x03==========
下面提供n<=10的情况：
f(1,1) = 1
f(2,2) = 3
f(3,3) = 10
f(4,4) = 35
f(5,5) = 126
f(6,6) = 462
f(7,7) = 1716
f(8,8) = 6435
f(9,9) = 24310
f(10,10) = 92378
蛋疼的同学可以拿去验证以下
?
