Q:
前段時間筆試文判，遇到了以前學的一個算法过椎，大學時沒認真想，只是記著怎么寫戏仓，現在得空疚宇，總結一下這個問題的解法。題目如下：
有個小孩正在上樓梯赏殃，樓梯有n階臺階敷待，小孩一次可以上1階、2階或3階仁热。實現一個算法榜揖，計算小孩有多少種上樓梯的方式。輸入n抗蠢，返回一個整數举哟。
A:
老師當年說呦，這個題目可以用遞歸迅矛，求出n-1妨猩，n-2，n-3級臺階的總和秽褒，就是答案壶硅。但是為啥嘞威兜，我來解釋一哈;
-
因為每次只能走1，2庐椒，3階牡属，所以，當一共5級臺階時扼睬，可以看成在走了4階基礎上再跨1階 + 走了3階基礎上再跨2階 + 走了2階基礎上再跨3階逮栅。示例圖如下??：
臺階排列圖解.jpg
- 因此，對于n階臺階窗宇，可以看成走了n-1階基礎上再跨1階 + 走了n-2階基礎上再跨2階 + 走了n-3階基礎上再跨3階措伐。
即：f(n): f(n-1) + f(n-2) + f(n-3)
代碼如下：（OC，遞歸）
- (int)countBySteps:(int)steps
{
int count = 0;
if (steps == 0) {
return 0;
}
if (steps == 1) {
return 1;
}else if (steps == 2){
return 2;
}else if (steps == 3){
return 4;
}else if (steps > 3){
return [self countBySteps:steps-1] + [self countBySteps:steps-2] + [self countBySteps:steps-3];
}
return count;
}
測試：
int stepNum = 15;
NSLog(@"A %d級臺階军俊，共有上樓方式%d種",stepNum,[self countBySteps:stepNum]);
下面討論侥加，一次可以跨不止3級的情況，題目改成如下：
這小屁孩的老師作業(yè)留少了粪躬，閑著沒事爬樓梯担败，樓梯有s階臺階(steps)，小孩一次可以上m階（maxStep）镰官。計算小孩有多少種上樓梯的方式提前。輸入s,m，返回一個整數泳唠。
由上例得：f(n) = f(n-1) + f(n-2) + f(n-3)狈网，
那么當最多跨m階時為：f(s,m) = f(s-1) + f(s-2) + f(s-3) + ··· + f(s-m)
那么先按最簡單遞歸法寫，哈哈哈笨腥，原諒我比較懶拓哺，其他方法會后續(xù)再補充，也歡迎大家一起討論~參照上例思路脖母，我們可以在遞歸里分為兩大部分士鸥，一部分是 steps > maxStep 時，參照f(s,m) = f(s-1) + f(s-2) + f(s-3) + ··· + f(s-m)進行累加谆级。
-
我們現在看 steps <= maxStep 時烤礁，怎么給出類似上例里 f(2)，f(3)的返回值哨苛。其實鸽凶，上例中的f(3)币砂，就是臺階一共3級建峭，最大可以跨三步的值，即f(2) 就是 f(2,2)决摧，f(3)就是f(3,3)亿蒸，你好好想想是不是這個理兒~
所以凑兰，f(m,m)的圖解如下??：
f(m,m)圖解.jpg
根據以上得出：
steps > maxStep 時，f(s,m) = f(s-1) + f(s-2) + f(s-3) + ··· + f(s-m);
steps <= maxStep時边锁，f(m,m) = f(m,m-1) +1;
steps = 1時姑食，return 1;
steps = 0時，return 0;
- so茅坛，算法如下：
- (int)countBySteps:(int)steps MaxStep:(int)maxStep
{
int count = 0;
if (steps == 0) {
return count;
}
if (steps == 1) {
count = 1;
}else{
if (steps > maxStep) {
for (int i = 1; i <= maxStep; i++) {
count += [self countBySteps:(steps - i) MaxStep:maxStep];
}
}else{
count = [self countBySteps:steps MaxStep:(steps - 1)] + 1;
}
}
return count;
}
測試??：
int stepNum = 15;
int maxStep = 3;
NSLog(@"A %d級臺階音半，共有上樓方式%d種",stepNum,[self countBySteps:stepNum]);
NSLog(@"B %d級臺階，共有上樓方式%d種",stepNum,[self countBySteps:stepNum MaxStep:maxStep]);
