如何实现DFS记忆化数组来优化不同路径的搜索？

本文共计1056个文字，预计阅读时间需要5分钟。

前言：DFS作为深度优先遍历，常遇到需要多次遍历的情况，导致时间复杂度呈指数级别。反复遍历目标并非单一访问节点，而是需要该节点达到某种状态（抽象）。

前言

DFS作为深度优先遍历，经常碰到需要一节点多次被遍历的情况，导致时间复杂度呈指数级。往往重复遍历目的就不是单词的访问节点了，而是需要该节点到某终点的一种状态（抽象），可用变量记录该节点的状态，将下一次dfs终止在此处，大大降低时间复杂度，这就是记忆化搜索。而记忆化搜索往往和动态规划关联。

一、不同路径

二、dfs & dp

dfs靠着高时间复杂度，尽量少浪费空间。而其指数级复杂度往往不合题意，则需要用空间换时间，采用dp来递推问题。

1、记忆化数组

/* target：从一个格子到另一个格子的不同路径数。 限制：只能走右和下。 idea1：直接dfs，能走到末尾，就return 1，回溯时把return回来的路径相加，即为某点出发的不同路径数。 idea2：右走和下走，也会导致走到同一个格子，所以有些格子被dfs了很多次，所以用一个数组来记录已被计算过的路径数。 idea3：dfs回溯时把每个格子当起点，如果把每个格子当作终点，由于右走和下走，所以每个格子的路径数是左边格子和上面格子的路径数之和。 */ // idea2:dfs + 数组。