題目：一個(gè)臺(tái)階總共有n級(jí)，如果一次可以跳1級(jí)，也可以跳2級(jí)。求總共有多少總跳法，并分析算法的時(shí)間復(fù)雜度。
分析：這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司都曾先后選用過個(gè)這道題作為面試題或者筆試題。
首先我們考慮最簡(jiǎn)單的情況。如果只有1級(jí)臺(tái)階，那顯然只有一種跳法。如果有2級(jí)臺(tái)階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1級(jí);另外一種就是一次跳2級(jí)。
現(xiàn)在我們?cè)賮碛懻撘话闱闆r。我們把n級(jí)臺(tái)階時(shí)的跳法看成是n的函數(shù)，記為f(n)。當(dāng)n>2時(shí)，第一次跳的時(shí)候就有兩種不同的選擇：一是第一次只跳1級(jí)，此時(shí)跳法數(shù)目等于后面剩下的n-1級(jí)臺(tái)階的跳法數(shù)目，即為f(n-1);另外一種選擇是第一次跳2級(jí)，此時(shí)跳法數(shù)目等于后面剩下的n-2級(jí)臺(tái)階的跳法數(shù)目，即為f(n-2)。因此n級(jí)臺(tái)階時(shí)的不同跳法的總數(shù)f(n)=f(n-1)+(f-2)。
我們把上面的分析用一個(gè)公式總結(jié)如下：
/ 1 n=1
f(n)= 2 n=2
\ f(n-1)+(f-2) n>2
分析到這里，相信很多人都能看出這就是我們熟悉的Fibonacci序列。至于怎么求這個(gè)序列的第n項(xiàng)，請(qǐng)參考本面試題系列第16題，這里就不在贅述了。
基于前面的分析，我們可以寫出如下的參考代碼：
#include
/////////////////////////////////////////////////////////////////////////////
// Given a push order of a stack, determine whether an array is possible to
// be its corresponding pop order
// Input: pPush - an array of integers, the push order
// pPop - an array of integers, the pop order
// nLength - the length of pPush and pPop
// Output: If pPop is possible to be the pop order of pPush, return true.
// Otherwise return false
/////////////////////////////////////////////////////////////////////////////
bool IsPossiblePopOrder(const int* pPush, const int* pPop, int nLength)
{
bool bPossible = false;
if(pPush && pPop && nLength > 0)
{
const int *pNextPush = pPush;
const int *pNextPop = pPop;
// ancillary stack
std::stackstackData;
// check every integers in pPop
while(pNextPop - pPop < nLength)
{
// while the top of the ancillary stack is not the integer
// to be poped, try to push some integers into the stack
while(stackData.empty() || stackData.top() != *pNextPop)
{
// pNextPush == NULL means all integers have been
// pushed into the stack, can't push any longer
if(!pNextPush)
break;
stackData.push(*pNextPush);
// if there are integers left in pPush, move
// pNextPush forward, otherwise set it to be NULL
if(pNextPush - pPush < nLength - 1)
pNextPush ++;
else
pNextPush = NULL;
}
// After pushing, the top of stack is still not same as
// pPextPop, pPextPop is not in a pop sequence
// corresponding to pPush
if(stackData.top() != *pNextPop)
break;
// Check the next integer in pPop
stackData.pop();
pNextPop ++;
}
// if all integers in pPop have been check successfully,
// pPop is a pop sequence corresponding to pPush
if(stackData.empty() && pNextPop - pPop == nLength)
bPossible = true;
}
return bPossible;
}
