有三種走樓梯方式，走完100階總共有多少種走法

原題：
有一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;
}