有没有近期RENEW过EAD和AP的# EB23 - 劳工卡
p*o
1 楼
这两天在专攻DP,慢慢的有了一些理解,在这里写一写,如果领悟正确可以帮跟我一样
挣扎的人省些时间,如果不对正好可以请高手指点。
个人感觉DP的要点是在通过caching来减少搜索的次数。比如上次我在这里问的那个
LeetCode的问题,Unique Paths II。首先考虑不用DP而用简单的DFS或者BFS,如果两
条路径共享一部分的话,共享的这部分就会被搜索两次。而用DP就可以克服这个重复搜
索的问题,从而达到节省一部分时间的目的。对于这个题目,DP不能提高时间复杂度,
因为这题本来就是NP-complete --不论用什么方法,所有路径都被看一遍才能知道结
果。但是由于prune掉很多不必要的搜索,还是可以提高效率。
挣扎的人省些时间,如果不对正好可以请高手指点。
个人感觉DP的要点是在通过caching来减少搜索的次数。比如上次我在这里问的那个
LeetCode的问题,Unique Paths II。首先考虑不用DP而用简单的DFS或者BFS,如果两
条路径共享一部分的话,共享的这部分就会被搜索两次。而用DP就可以克服这个重复搜
索的问题,从而达到节省一部分时间的目的。对于这个题目,DP不能提高时间复杂度,
因为这题本来就是NP-complete --不论用什么方法,所有路径都被看一遍才能知道结
果。但是由于prune掉很多不必要的搜索,还是可以提高效率。