简略解释一下为什么运用两次动规得出的不一定是最大值,但不代表思路错误
查看原帖
简略解释一下为什么运用两次动规得出的不一定是最大值,但不代表思路错误
909893
zlx578楼主2023/8/23 20:17
动规的主要思想还是记忆化暴力枚举,枚举所有出现的情况。
我们在第一次进行动规的时候可以得出第一条路径的最大值,但是这一条路径不一定是唯一的,这就导致会影响到第二条路径的路线动规得出来的最大值。
如果说你把所有的第一次路径最优解的路线全部列举一遍,然后在这个基础上去进行第二次动规,算出的最大值就是真正的答案,所以很多人两次二维dp得出的结果并没有涵盖所有的情况,因为第一次的路线并不一定唯一,其实这个思路是正确的,但是很多人会错是因为中间有些值得思考的地方没有考虑到,当然,如果你按照这个思路编写代码当然也是可以的,但是效率上还是比不上四维dp,因为动规的使用是为了提高效率,所以如果愿意以两次二维dp去实现当然也是行的,毕竟这个测试集比较水。
0 1 0 1 0
0 1 0 0 0
0 0 0 0 0
0 0 0 1 0
0 1 0 1 0
比如这个测试集,第一次路径最大值是4,但是最优路径有很多种,如果你的第一次路线没有枚举完全,比如我第一次的路线只考虑到(1,1)->(1,2)->(2,2)->(2,4)->(5,4)->(5,5),就可能导致你的第二次路线不能取完所有的1,导致得出的结果是5,但实际上最大值是6(自己可以检验一下),我有解释不充分的地方,欢迎各位来讨论补充
2023/8/23 20:17
加载中...