@[Polaris_blig](/space/show?uid=179809) 你这样没法判断i取了没,你要把所有状态记录下来开n维数组才行,而完全不必记录,你真想用记搜要多开一维记录取到第几个了,如前x个物品用y时
by 20140408abcd @ 2019-08-06 18:03:52
接下来在x+1~n中取
by 20140408abcd @ 2019-08-06 18:04:53
可这样无法用滚动数组取掉一维,时间差不多,空间被吊打,编程复杂度极大
by 20140408abcd @ 2019-08-06 18:06:44
一般来说死在空间
by 20140408abcd @ 2019-08-06 18:07:27
@[20140408abcd](/space/show?uid=136928) 啊！您好！谢谢，但是还是不太懂为什么无法判断i取了没有，用vis数组不可以吗？
by Polaris_blig @ 2019-08-06 19:20:35
@[20140408abcd](/space/show?uid=136928) vissub用来标记是否取i
by Polaris_blig @ 2019-08-06 19:21:51
@[Polaris_blig](/space/show?uid=179809) 举个例子
```
2 3
1 1
1 1
1 2
```
你先通过取1,2种得到了d[2]=2;你回溯取1,3种程序发现已求返回d[2]=2,而正确是d[2]=3;所以你要多开一维即d[v][pos]表示在前pos件里花v时的最大价值,记忆化搜索优点是方程好列,但是必须记录所有状态,你这题就是没记录所有状态才出错,而在一些阶段明显的dp常常可用滚动数组省空间,所以各有所长
by 20140408abcd @ 2019-08-07 08:35:59
@[Polaris_blig](/space/show?uid=179809) 因为d数组里不一定是花s时的最优值,但必是取前pos个的最优值,
by 20140408abcd @ 2019-08-07 08:40:47
@[Polaris_blig](/space/show?uid=179809) 再者,你d数组里的取法有可能与当前取法冲突,例子不好找我就不说了
by 20140408abcd @ 2019-08-07 08:44:18
在阶段明显的题中还是用普通dp吧
by 20140408abcd @ 2019-08-07 08:53:17