1190：上台阶 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 59792 通过数: 20101 【题目描述】 楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。 【输入】 输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。 【输出】 每一行输出对应一行输入的结果，即为走法的数目。 【输入样例】 1 2 3 4 0 【输出样例】 1 2 4 7

这是一道经典的动态规划问题，可以使用递推公式进行求解。

设 f(n) 表示到第 n 级台阶的不同走法数目，考虑最后一步的情况：

1. 如果最后一步只跨了一级台阶，则前面共有 f(n-1) 种不同的走法；

2. 如果最后一步跨了两级台阶，则前面共有 f(n-2) 种不同的走法；

3. 如果最后一步跨了三级台阶，则前面共有 f(n-3) 种不同的走法。

因此，可以得到递推公式：f(n) = f(n-1) + f(n-2) + f(n-3)。

边界条件为：f(1) = 1, f(2) = 2, f(3) = 4。

以下是代码实现：