关于滚动数组
  • 板块学术版
  • 楼主iamajcer
  • 当前回复4
  • 已保存回复4
  • 发布时间2025/7/26 15:48
  • 上次更新2025/7/26 21:44:13
查看原帖
关于滚动数组
629377
iamajcer楼主2025/7/26 15:48

我的 DP 真的是太差了,所以问题有点多,而且可能有些比较傻,希望大佬能耐心看看,感激不尽!!可以玄关。

1.要滚动的那一维,在循环更新 dp 值的时候,是不是要提到循环的最前面?

2.每次滚动计算完当前层,在计算下一层时是不是应该先清空?但如果只是赋值操作,没有累加,取最值等等是不是就不需要清空了(例如 01背包)?

3.如果有多维需要滚动,应该如何维护?(属于是对问题 1 的疑问了,这里应该怎么安排循环顺序?)比如说:

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 应该如何维护?就是不仅仅关系到上一层状态,而是多层状态。比如:

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

2025/7/26 15:48
加载中...