求大神做一下题目。连线题目

题目的意思是让你上n级的楼梯,每次可以走12,3级3种选择,那么走到n级一共有几种组合

首先令f(n)为上n级楼梯总的方法数



额……不好意思繁体字不太懂……囧
你问的是,为什么时间复杂度是O(N)但没开什么空间?
时间和空间复杂度在这里这么理解吧
就是通过另开一个数组记录当前已经跑过的节点(实际上這个数组可以合并到dp[]数组)
这里就是通过一定量的空间牺牲(另开一个数组;甚至不需要另外再开一个直接用dp[]就行,这样就毫无牺牲之說)
来换取时间复杂度的大量缩减
}

我要回帖

更多关于 连线题目 的文章

更多推荐

版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。

点击添加站长微信