回溯
今天自己去解了一道组合的问题,从循环暴力慢慢走到回溯的思路,今天就挺明白了。
凡是排列组合问题,正常的循环处理不了。刚好回溯就很好的解决了这类问题,所以这类问题首要考虑回溯的方法,如分割等和子集问题,虽然会超时,但不失为一个解决思路。
处理排列组合问题首要考虑回溯法。模板如下,可以去除重复元素
排列组合问题回溯,那个for循环没有问题,但是如果存在回溯,但不是排列问题,就不能要那个for循环了,因为不能把后面的元素拿到前面来。
比如:下面的例子:
可以看到代码没有for,因为是按照顺序递归
动态规划
有些问题,比如字符串匹配,很明显需要n的平方的时间复杂度,而且存在重复问题,那么就需要设立标志位,这时可以考虑动态规划。有通用模板