原题：
有一100阶层的楼梯，有三种走楼梯方式，一次走一阶，一次走两阶，一次走三阶。用算法实现，走完100阶总共有多少种走法
解答：
f(n)=f(n-1)+f(n-2)+f(n-3）
有两个要点：1，结果大于int32，需要用到高精度。 2，直接递归会有大量重复运算，需要缓存每一步的结果

#include "stdio.h"

void addCache(char count[], char d[]);
void reverse(int index);
void lastMove(int stepOver);

char result[100];
char cache[101][100];

void main()
{
for (int i = 0; i < 101; i++)
{
cache[i][0] = 0;
for (int j = 1; j < 100; j++)
{
cache[i][j] = 0;
}
}
cache[0][0] = '0';
cache[1][0] = '1';
cache[2][0] = '2';
cache[3][0] = '4';

int floor = 100;
lastMove(floor);

reverse(floor);
printf("total: %s", result);
}

void lastMove(int stepOver)
{
if (stepOver > 3)
{
for (int i = 1; i <= 3; i++)
{
int index = stepOver - i;
if (cache[index][0] == 0)//not cached
{
lastMove(index);
}
addCache(cache[stepOver], cache[index]);
}

}
else
{
printf("error\n");
}
}

void addCache(char count[], char d[])
{
int j = 0;
while (d[j] != 0)
{
int in = d[j] - '0';
for (int i = j; i < 100; i++)
{
if (in == 0)
{
break;
}
if (count[i] == '\0')
{
count[i] = '0';
}

int curNum = count[i] - '0' + in;
if (curNum > 9)
{
in = curNum / 10;
curNum -= in * 10;
}
else
{
in = 0;
}
count[i] = curNum + '0';
}

j++;
}

}

void reverse(int index)
{
int length = 0;
for (int i = 0; i < 100; i++)
{
if (cache[index][i] == 0)
{
length = i;
break;
}
}

for (i = 0; i < length; i++)
{
result[length - 1 - i] = cache[index][i];
}
result[length] = 0;
}