DFS, record the state, if come into a state appeared before , ignore it.
DFS is very slow, can anybody give some hints to DP?

Это и есть ДП. Ведь ты переходишь по сути в известные состояния(т.е.уже просмотренные) и новые,для которых рассматриваешь переходы.Просто у нас не совсем стандартные размерности "подзадачи".
ДП-это не только реккурентные соотношения.