讨论/算法和数据结构/有个基于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规模(轮数),就能寻址得到一块空间适当的内存,避免移动的开销。

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

展开讨论
bit_cabinzkk发起于 2020-03-03
共 2 个讨论

感觉没什么问题吧...
可以使用双端队列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

华为直招稀缺java开发岗

1、负责华为研发IT系统的概要设计工作,核心功能代码开发。
2、技术疑难杂症,紧急生产问题处理。
3、对主流PDM、ERP、数据管理、大数据产品有深入的了解,熟悉企业产品开发业务过程。
4、 熟悉J2EE企业应用开发,具有丰富的大型Web项目开发经验
精通JAVA、JSP、XML、HTML技术,熟悉数据库开发,熟悉UNIX/LINUX操作系统。
5、具有较强的面向对象分析及设计能力,丰富的软件架构设计经验,熟悉UML建模。
6、 熟悉Spring Boot、Spring Cloud、Netflix微服务框架。
7、985、211学校优先,产品生命周期管理、windchill软件包、ERP软件包、数据治理,数据管理相关工作经验优先。
8、毕业证、学位证、***。
9、有5-10年工作经验,20-40K/月
联系方式:13719220844( 微信 )/yaohongzhen@huawei.com

华为2020届校招软件类补招
1、2020年应届校招生。(国内院校:2020届毕业的本硕博同学;国外院校:毕业时间在2019.1-2020.12期间毕业的本硕博同学)
2、软件通信类专业
3、开发测试类岗位
联系方式:13719220844( 微信 )/yaohongzhen@huawei.com