动态规划与搜索算法

动态规划（Dynamic Programming, DP）

动态规划是一种解决优化问题的算法设计技术，主要用于求解具有重叠子问题和最优子结构特性的最优化问题。在动态规划中，我们会将复杂问题分解为多个子问题，并计算子问题的解，然后通过组合子问题的解来构造原问题的解。通常，动态规划过程中会构建一张表格（或称为状态转移表），存储已经计算过的子问题的解，避免重复计算，从而降低时间复杂度。

搜索算法

（如深度优先搜索DFS、广度优先搜索BFS、Dijkstra算法、A*搜索等）则是用来探索图或树状结构以找到满足某种条件的路径或解的一种方法。搜索算法通常不强调重叠子问题和最优子结构，其重点在于遍历可能的解决方案空间，直至找到符合条件的目标状态。

区别：

1. 目的：动态规划主要用于求解最优化问题，而搜索算法主要用于找到从起点到终点的路径或其他满足条件的状态。

2. 记忆化：动态规划往往涉及记忆化（Memoization）或填表，存储已经计算过的子问题答案以减少重复计算。搜索算法中也有类似的概念，如记忆化搜索，但它更侧重于避免回溯过程中的重复状态探索。

3. 空间消耗：动态规划往往需要额外的空间存储中间结果，搜索算法则通常需要栈（DFS）或队列（BFS）来跟踪搜索路径，两者都会占用额外空间，但动态规划的记忆化表一般会更大。

具体事例：

• 动态规划例子：斐波那契数列问题。要求计算第n个斐波那契数（F[n]），定义为F[0]=0, F[1]=1，F[n]=F[n-1]+F[n-2]。动态规划方法会创建一个数组来存储F[0]到F[n-1]的值，通过递推关系计算，避免了重复计算子问题。

for (int i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
}

• 搜索算法例子：迷宫问题。从起点出发寻找一条到达终点的路径。深度优先搜索会在搜索过程中标记已访问节点，以防回溯，一旦找到终点，返回路径。

bool dfs(Maze maze, Position current, Position target) {
   if (current == target) return true;
  maze[current] = Visited; // 标记已访问
   for (Position neighbor : maze.neighbors(current)) {
       if (!maze.isWall(neighbor) && !maze.isVisited(neighbor)) {
            if (dfs(maze, neighbor, target)) {
                maze.addPath(current, neighbor); // 记录路径
                return true;
            }
        }
    }
    return false; // 没有找到路径
}

在这两个例子中，斐波那契数列问题利用了动态规划减少了重复计算，而迷宫问题则是通过搜索算法探索可能的路径来找到解。