T******7
发帖数: 1419 | 1 用dynamic programming的方法。
另外，如果我用纯c做这个题目 没有hashmap。怎么解决？还能得到相同的时间复杂度
么 |
l*********8
发帖数: 4642 | 2 problem:
有一段楼梯有n级台阶,规定每一步只能跨一级或两级或三级,要登上第n级台阶有几种不
同的走法?
solution:
let f(i) denote the number of different methods to climb the stairs.
Then
f(0) = 1
f(1) = 1
f(2) = 2
f(3) = f(0) + f(1) + f(2)
....
f(n) = f(n-3) + f(n-2) + f(n-1)
Is this what you talked about?
【在 T******7 的大作中提到】
: 用dynamic programming的方法。
: 另外，如果我用纯c做这个题目 没有hashmap。怎么解决？还能得到相同的时间复杂度
: 么
|
c****p
发帖数: 6474 | 3 好像递推公式有点问题？
【在 l*********8 的大作中提到】
: problem:
: 有一段楼梯有n级台阶,规定每一步只能跨一级或两级或三级,要登上第n级台阶有几种不
: 同的走法?
: solution:
: let f(i) denote the number of different methods to climb the stairs.
: Then
: f(0) = 1
: f(1) = 1
: f(2) = 2
: f(3) = f(0) + f(1) + f(2)
|
l*********8
发帖数: 4642 | 4 let me think again....
【在 c****p 的大作中提到】
: 好像递推公式有点问题？
|
c****p
发帖数: 6474 | 5 类fabonacci的问题应该都能得到复杂度为logn的解吧？
【在 T******7 的大作中提到】
: 用dynamic programming的方法。
: 另外，如果我用纯c做这个题目 没有hashmap。怎么解决？还能得到相同的时间复杂度
: 么
|
c****p
发帖数: 6474 | 6 好像是我想错了。。。
【在 c****p 的大作中提到】
: 好像递推公式有点问题？
|
l*********8
发帖数: 4642 | 7 I think it's correct.
【在 c****p 的大作中提到】
: 好像递推公式有点问题？
|
g*********e
发帖数: 14401 | 8 the runtime is O(n) space requirement is O(k) where k is the number of
different steps you can make each time. |
c****p
发帖数: 6474 | 9 logk的时间复杂度和O(1)的空间复杂度就够了吧。。。
【在 g*********e 的大作中提到】
: the runtime is O(n) space requirement is O(k) where k is the number of
: different steps you can make each time.
|
l*********8
发帖数: 4642 | 10 应该是： O(k^3 * logn) 时间
O(k^2) 空间 吧？？
【在 c****p 的大作中提到】
: logk的时间复杂度和O(1)的空间复杂度就够了吧。。。
|
|
|
c****p
发帖数: 6474 | 11 嗯，我那里的k就是n
【在 l*********8 的大作中提到】
: 应该是： O(k^3 * logn) 时间
: O(k^2) 空间 吧？？
|
p*****2
发帖数: 21240 | 12 run time 为什么是logn呢？
不是要从1算到n吗？ |
l*********8
发帖数: 4642 | 13 好像在CLRS 五六十页的地方讲过
【在 p*****2 的大作中提到】
: run time 为什么是logn呢？
: 不是要从1算到n吗？
|
l*****a
发帖数: 14598 | 14 fibonacci serials
有个著名的log2n算法
不过我觉得面世中回答那个或者面试者要求那个
的话
真是无聊
【在 p*****2 的大作中提到】
: run time 为什么是logn呢？
: 不是要从1算到n吗？
|
c****p
发帖数: 6474 | 15 [f1 f2 f3] = [f0 f1 f2] * A，
A= [0 0 1; 1 0 1; 0 1 1];
这样[fn fn+1 fn+2] = [f0 f1 f2] * A^n
其中A^n可以用二分法算，logn【 在 peking2 (myfacebook) 的大作中提到: 】 |
p*****2
发帖数: 21240 | 16
mark一下先。多谢。
【在 c****p 的大作中提到】
: [f1 f2 f3] = [f0 f1 f2] * A，
: A= [0 0 1; 1 0 1; 0 1 1];
: 这样[fn fn+1 fn+2] = [f0 f1 f2] * A^n
: 其中A^n可以用二分法算，logn【 在 peking2 (myfacebook) 的大作中提到: 】
|
s******n
发帖数: 3946 | 17 费波纳切不是O(1)的时间复杂度么，这个推推也能搞出个公式吧 |
a********m
发帖数: 15480 | 18 为啥A是[0 0 1; 1 0 1; 0 1 1]? 感觉是010; 001; 111，或者是俺想差了？
【在 c****p 的大作中提到】
: [f1 f2 f3] = [f0 f1 f2] * A，
: A= [0 0 1; 1 0 1; 0 1 1];
: 这样[fn fn+1 fn+2] = [f0 f1 f2] * A^n
: 其中A^n可以用二分法算，logn【 在 peking2 (myfacebook) 的大作中提到: 】
|
l*********8
发帖数: 4642 | 19 你说的是这个吧：
Fn 约等于 1/sqrt(5) * （1.618...）^ n (黄金分割数的n次方）
算n次方也要O(logn)的
【在 s******n 的大作中提到】
: 费波纳切不是O(1)的时间复杂度么，这个推推也能搞出个公式吧
|
