#include <stdio.h>

int count = 0;
char str[100];

void search(int nStaircases, int nSteps = 0)
{
    if (nStaircases < 0) // 不能多走幾階梯
        return;
    if (nStaircases == 0) // 走完了所有階梯時
    {
        if (nSteps % 2 == 0) // 走了剛好偶數步
        {
            str[nSteps] = '\0';
            //puts(str);
            count++; // 方案可行
        }
        return;
    }
    
    str[nSteps] = '1';
    search(nStaircases - 1, nSteps + 1); // 走一步
    str[nSteps] = '2';
    search(nStaircases - 2, nSteps + 1); // 走兩步
}

int main(void)
{
    search(39);
    printf("%d\n", count);
    return 0;
}

這道題比較簡單，關鍵是要讀懂題。
其實就是要求計算偶數個1和2相加等於39的算式有多少個。