动态规划：解决最短路径问题及递归式APSP

"APSP:递归式-动态规划" 动态规划是一种强大的算法设计策略，它通过解决子问题并存储结果来避免重复计算，从而提高效率。在动态规划中，通常涉及将大问题分解为相互关联的小问题，并利用这些小问题的最优解来构建原问题的最优解。 在APSP（All Pairs Shortest Paths）问题中，目标是找到图中所有顶点对之间的最短路径。递归式如下： 对于任意k > 0， c(i, j, k) = min{c(i, j, k-1), c(i, k, k-1) + c(k, j, k-1)} 这个递归式描述了从顶点i到顶点j的最短路径可能经过中间顶点k的情况。其中，c(i, j, k)表示从i到j经过k步的最短路径的长度。当k等于0时，这意味着没有中间顶点，即c(i, j, 0)是i到j的直接边的权重。 有两个关键性质： 1. c(i, k, k-1) = c(i, k, k)，因为在k-1步到达k后，不需要额外的步骤。 2. c(k, j, k) = c(k, j, k-1)，因为已经到达k，不需要再走回k。 直接使用递归公式会导致计算c(i, j, n)的复杂度极高，为O(n^3)，这在处理大规模问题时是不可接受的。因此，通常采用迭代方法来优化计算过程，将时间复杂度降低到O(n^3)。迭代算法的伪代码未在描述中给出，但通常包括一个三层循环，分别遍历源点、中间点和目标点，逐步更新所有顶点对的最短路径。 动态规划广泛应用于各种问题，如： 1. 0/1背包问题：在容量有限的背包中选择物品，使得总价值最大化，每个物品要么全部放入，要么不放。 2. 矩阵乘法链问题：寻找最小代价的矩阵乘法顺序。 3. 最短路径问题：APSP是其中的一个例子，还有单源最短路径问题，如Dijkstra算法或Floyd-Warshall算法。 4. 最大非交叉子集问题：在给定网络中寻找最大的互不相交的子网。 5. 最长公共子序列：找到两个序列的最长子序列，该子序列在原序列中都存在，但不一定连续。 6. 隐马尔可夫模型：在概率建模中用于处理序列数据，如自然语言处理。 动态规划的核心思想是利用最优子结构和重叠子问题。通过备忘录或自底向上的方式存储和重用子问题的解，动态规划可以解决许多复杂的问题，而避免了冗余计算。这种算法在计算机科学的许多领域都有广泛应用，如图论、组合优化、字符串处理等。