【原创】如果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



蛋疼的同学可以拿去验证以下