讨论/算法和数据结构/有个基于Python3的一点关于dp的思考和疑问/
有个基于Python3的一点关于dp的思考和疑问

有个基于Python3的一点关于dp的思考和疑问,想和大家交流:

当每轮dp实现只涉及到之前的相邻K项时,有两种实现方案:

①维护K+1个变量,每轮计算出新的一项第(K+1)项,再将所有已知数据的后K个往前覆盖一位,腾出第K+1个变量用于下次计算。
②直接用一个list不断地append即可。

空间上:①是更加节省的,相比于②的复杂度是dp轮数N相关的 O(N), ①只需要O(K)。

时间上:但是①每轮中都需要一次 O(K) 的覆盖数据时间开销,如果要避免开销,可以使用类似C静态数组中的求余循环,但是求余也有额外的时间开销。相反,②的append就是 O(1) 的,所以可能会更快。

但是,需要注意到②中使用的list底层仍然是数组,当动态增加的list所在的内存段空间不足时,list的地址会发生一次与当前历史dp规模相当的数据移动,这时又有了最坏情况O(N)。所以如果在dp开始前就把list的长度初始化为即将进行的dp规模(轮数),就能寻址得到一块空间适当的内存,避免移动的开销。

想知道我的这些思考是否有不正确的地方,或可以改进的地方?

展开讨论

感觉没什么问题吧...
可以使用双端队列deque来减少复杂度.
可以右侧插入K+1,从左侧弹出一项,这个操作都是O(1)的
伪代码大概这样子

from collections import deque
dp = deque([None] * k)
# 初始化dp数组
initial_dp(dp)
# 计算第K +1 项
temp = compute(dp)
# 插入 K+1 弹出 第0 项
dp.popleft()
dp.append(temp)

BIT是魏公村的BIT么hhh

展开全部 2 讨论