京東2016算法工程師筆試題（登樓梯）

有一段樓梯臺階有15級臺階，以小明的腳力最多可以一次跨上三級臺階，問有多少種方法登上這段樓梯？

#include<iostream>using namespace std;int compute(int n){       int sum=0; //統(tǒng)計	if(n==1)sum=1;	else if(n==2)sum=2;	else if(n==3)sum=4;//登上一節(jié)臺階的方法只有一種，兩級臺階的方法有兩種，三級臺階有四種{（1,1,1）(1,2) (2,1) (3) }   動態(tài)規(guī)劃的方法	else	{	  sum=compute(n-1)+compute(n-2)+compute(n-3);    }	return sum;}int main(){	cout<<compute(15)<<endl;	return 0;}
什么是拓?fù)渑判?nbsp;？  一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進(jìn)行拓?fù)渑判颍菍中所有頂點(diǎn)排成一個線性序列，使得圖中任意一對頂點(diǎn)u和v，若<u，v> ∈E(G)，則u在線性序列中出現(xiàn)在v之前。
 有向無環(huán)圖才存在拓?fù)湫蛄?/h2>
對于一個DAG,可能存在多個拓?fù)湫蛄?/h2>
除首任務(wù)開始不需要條件，其它任務(wù)的執(zhí)行必須在它的前驅(qū)任務(wù)完成才能執(zhí)行（選擇一個沒有前驅(qū)的頂點(diǎn),刪除該頂點(diǎn)和所有以它為起點(diǎn)的有向邊,循環(huán)直到DAG為空）
名企筆試：滴滴出行2017秋招算法筆試題（拓?fù)渑判颍?/h2>
下面哪個序列不是上圖的一個拓?fù)渑判颍?/p>
A. ebfgadch
B. adchebfg
C. aebdgfch
D. aedbfgch
選擇B
騰訊2016校園招聘研發(fā)工程師筆試題（全連通圖）
n個頂點(diǎn),m條邊的全連通圖，至少去掉____邊才能構(gòu)成一棵樹？
A. n-1
B. m-1
C. m-n+1
D. m-n-1
N個點(diǎn)如果相連至少n-1條，現(xiàn)在我們有m條邊，所以至少減少m-(n-1)
所以選擇C