社区讨论

关于滚动数组

学术版参与者 5已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mdjy9qxx
此快照首次捕获于
2025/07/26 15:49
7 个月前
此快照最后确认于
2025/11/04 03:41
4 个月前
查看原帖
我的 DP 真的是太差了,所以问题有点多,而且可能有些比较傻,希望大佬能耐心看看,感激不尽!!可以玄关。
1.要滚动的那一维,在循环更新 dp 值的时候,是不是要提到循环的最前面?
2.每次滚动计算完当前层,在计算下一层时是不是应该先清空?但如果只是赋值操作,没有累加,取最值等等是不是就不需要清空了(例如 01背包)?
3.如果有多维需要滚动,应该如何维护?(属于是对问题 1 的疑问了,这里应该怎么安排循环顺序?)比如说:
CPP
for (int i=1; i<=n; i++)
	for (int j=1; j<=m; j++)
		for (int k=1; k<=5; k++) 
			f[i][j][k]+=f[i-1][j-1][k-p[i]]; 
4.滚动的不是 -1 应该如何维护?就是不仅仅关系到上一层状态,而是多层状态。比如:
CPP
for (int i=3; i<=n; i++)
	for (int j=1; j<=m; j++)
		f[i][j]=max(f[i-1][j], f[i-2][j], f[i-3][j]);
5.这份代码我暴力能过样例,但是滚动后过不了,也不知道哪里有问题,希望您看看: https://note.ms/rmcp

回复

7 条回复,欢迎继续交流。

正在加载回复...