我'm trying to solve the following problem from Skiena'的算法设计手册：
8-16考虑一个城市，其街道由X x Y网格定义 . 我们感兴趣的是从网格的左上角走到右下角 . 不幸的是，这个城市有不好的社区，我们不想走路的交叉点 . 我们给出一个X x Y矩阵BAD，其中BAD [i，j] =“是”当且仅当街道i和j之间的交叉点在附近避免 . （c）给出O（XY）算法以找到跨越网格的最短路径，以避免坏邻域 . 您可以假设所有块的长度相等 . 对于部分信用，给定O（X ^ 2 * Y ^ 2）算法 .
问题来自动态规划章节和“图形问题” Headers 下 . 我知道我可以将其建模为一个无向的未加权图形，其顶点为所有“好”交叉点和任何相邻“好”顶点之间的边 . 鉴于这是一个未加权的图形，我可以从左上顶点开始进行广度优先搜索，一旦到达右下顶点，我就有最短路径 .
鉴于此问题来自动态编程章节，我试图弄清楚如何使用动态编程来解决这个问题 . 到交叉点（i，j）的最短路径是到交叉点（i，j-1），（i-1，j），（i，j 1），（i 1，j）的最短路径的最小路径 . . 这个公式似乎不适合动态编程的重叠子问题 . 使用动态编程可以解决这个问题吗？
1 回答
实际上，该公式完全符合动态规划的重叠子问题本质 .
在第一顺序中，到交叉点的最短路径可以根据到相邻交叉点的最短路径来表达 . 因此，子问题 .
在第二顺序中，多个交叉点可以共享相同的相邻交叉点，其最短路径是每个其他交叉点的最短路径函数中的输入 . 因此，重叠的子问题 .
另外，Dijkstra算法和Bellman-Ford算法都是动态编程算法的例子，可以解决给定的大O复杂约束中的示例问题 .