昨天电话面试题
实习没找到，决定静下来看看书了，昨天电话面的题：
有1000个台阶，可以一次上一个台阶，可以一次上两个台阶，可以一次上三个台阶，上到第1000个台阶有多少种方式？
感觉用dp，最后也没想出来~~~反正没搞过acm，反正是杯具了
有1000个台阶，可以一次上一个台阶，可以一次上两个台阶，可以一次上三个台阶，上到第1000个台阶有多少种方式？
感觉用dp，最后也没想出来~~~反正没搞过acm，反正是杯具了
作者: dreamhunter_lan 发布时间: 2011-06-15
S(n) = s(n-1) + s(n-2) + s(n-3)
从1开始算，O（n）复杂度
从1开始算，O（n）复杂度
作者: oo 发布时间: 2011-06-15
其实这个题就有点像小学还没学二项式展开去求杨辉三角时用的那个方法
作者: keeya0416 发布时间: 2011-06-15
引用 1 楼 oo 的回复:
S(n) = s(n-1) + s(n-2) + s(n-3)
从1开始算，O（n）复杂度
S(n) = s(n-1) + s(n-2) + s(n-3)
从1开始算，O（n）复杂度
good，我想了半天也没想通，看来还是需要加深对dp的理解啊。
作者: gogdizzy 发布时间: 2011-06-15
1 L正解
作者: qq675927952 发布时间: 2011-06-15
引用 1 楼 oo 的回复:
S(n) = s(n-1) + s(n-2) + s(n-3)
从1开始算，O（n）复杂度
S(n) = s(n-1) + s(n-2) + s(n-3)
从1开始算，O（n）复杂度
1楼正解：
S(n) = s(n-1) + s(n-2) + s(n-3)； n > 3
s(1) = 1
s(2) = 2
s(3) = 3
证明：因为只允许可以一次上一个台阶，可以一次上两个台阶，可以一次上三个台阶。设到达第n个台阶(n>3)的方法只可能有：1）由第n-3个台阶一次上三个；2）由第n-2个台阶一次上两个；3）由第n-1个台阶一次上一个。
因此 即可求得通项公式：
S(n) = s(n-1) + s(n-2) + s(n-3)； n > 3
s(1) = 1
s(2) = 2
s(3) = 3
作者: wcyoot 发布时间: 2011-06-15
用矩阵乘法的话，还可以优化到log(n)
作者: litaoye 发布时间: 2011-06-15