dp的介绍

多段图问题的动态规划解法多段图问题指将图划分为多个阶段每个阶段包含若干节点只能从前一阶段的节点转移到当前阶段的节点。动态规划解法可高效求解最短路径问题。设c(i,j)为节点i到j的代价d(j)表示到达节点j的最短路径长度。状态转移方程为其中表示前一阶段的节点集合。// 假设有k个阶段nodes[k]存储第k阶段的节点 for(int stage 1; stage k; stage) { for(auto j : nodes[stage]) { int min_cost INT_MAX; for(auto i : nodes[stage-1]) { if(cost[i][j] dp[i] min_cost) { min_cost cost[i][j] dp[i]; } } dp[j] min_cost; } }动态规划与递推的复杂度对比递推通常指单向的状态转移时间复杂度为$O(n)$空间复杂度$O(1)$。例如斐波那契数列的递推实现仅需保存前两个状态。动态规划需要存储子问题的解时间复杂度和空间复杂度通常为$O(n^2)$或$O(nm)$。例如背包问题需要二维状态数组时间复杂度为$O(nW)$其中$W$为背包容量。动态规划通过记忆化存储避免了重复计算但空间开销更大。递推适用于无后效性问题而动态规划能处理更复杂的重叠子问题。动态规划的典型应用场景最短路径问题如Floyd算法和Dijkstra算法的变种利用动态规划记录中间节点距离。资源分配问题如背包问题通过状态转移方程决定最优物品组合。字符串处理如编辑距离问题用二维数组存储子串间的转换代价。序列比对在生物信息学中动态规划用于DNA序列匹配。游戏AI中的决策树评估通过状态缓存优化搜索过程。金融领域的期权定价模型使用动态规划计算最优执行策略。动态规划DP在多段图问题中的应用动态规划Dynamic Programming, DP通过将问题分解为子问题并存储子问题的解来优化计算效率。多段图Multistage Graph是经典的DP应用场景其特点是图中的节点被划分为多个阶段且边仅连接相邻阶段的节点。多段图的最短路径问题给定一个带权有向多段图求解从源点到终点的最短路径。定义d[i][j]表示从节点j到终点的最短距离状态转移方程为$$d[i][j] \min_{k \in \text{后继节点}}(d[i1][k] w(j, k))$$初始化时终点的距离为0其他节点初始化为无穷大。代码实现#include iostream #include vector #include climits using namespace std; int multistageShortestPath(vectorvectorpairint, int graph, int stages) { int n graph.size(); vectorint dp(n, INT_MAX); dp[n - 1] 0; // 终点距离为0 for (int i stages - 2; i 0; --i) { for (int j 0; j n; j) { if (graph[j].empty() || graph[j][0].first ! i 1) continue; for (auto edge : graph[j]) { int k edge.first; int w edge.second; if (dp[k] ! INT_MAX) { dp[j] min(dp[j], dp[k] w); } } } } return dp[0]; }DP与递推的复杂度对比时间复杂度递推直接按阶段计算每次需遍历所有可能的转移复杂度为 O(N^2)N 为节点数。DP通过记忆化存储子问题解避免重复计算复杂度优化至 O(N E)E 为边数。空间复杂度递推通常为 O(1)但若需存储中间结果可能升至 O(N)。DP需存储子问题解空间复杂度为 O(N)。DP的应用场景最优化问题如最短路径、背包问题、任务调度等。计数问题如路径计数、组合数学问题卡特兰数。序列问题如最长公共子序列LCS、最长递增子序列LIS。示例0-1背包问题状态转移方程int knapsack(vectorint weights, vectorint values, int capacity) { vectorint dp(capacity 1, 0); for (int i 0; i weights.size(); i) { for (int j capacity; j weights[i]; --j) { dp[j] max(dp[j], dp[j - weights[i]] values[i]); } } return dp[capacity]; }总结动态规划通过状态转移和记忆化显著提升效率适用于具有重叠子问题和最优子结构的问题。多段图问题展示了DP的阶段化处理思想而复杂度对比凸显了DP的优势。实际应用中需根据问题特点设计状态和转移方程。