力扣2646题：图论与动态规划解决最小化旅行的价格总和
4个月前 (08-18)
一、题目解读
本题要求在一个由边和价格构成的树形图中，通过指定旅行路径计算商品的最小总价格。每个节点代表商品，边表示路径，每次经过节点需支付对应价格。需设计策略使总价格最低，允许对任意节点的价格减半一次。题目核心在于路径统计与动态规划优化。
二、解题思路
2. 路径访问统计：使用BFS遍历旅行路径，记录每个节点被访问次数。
3. 动态规划：定义状态 dp[u][0/1] 表示节点u是否减半，递归计算子树最优值。
4. 关键优化：通过回溯路径累加访问次数，避免重复遍历；利用状态转移方程结合价格减半策略求解。
三、解题步骤
1. 构建树：遍历边列表，双向添加至邻接表。
2. 统计访问次数：对每个旅行路径，从起点BFS到终点，回溯路径并累加节点计数。
3. 动态规划求解：
○ 初始化：dp[u][0] = price[u] * count[u]（不减半），dp[u][1] = price[u] / 2 * count[u]（减半）。
○ 递归计算：遍历子节点v，根据父节点状态选择是否减半，合并子树结果。
4. 返回根节点最优值：min(dp[0][0], dp[0][1])。
四、代码及注释
class Solution {
public:
int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
// 构建邻接表表示的树
vector<vector<int>> tree(n);
for (const auto& edge : edges) {
tree[edge[0]].push_back(edge[1]);
tree[edge[1]].push_back(edge[0]);
}
// 统计每个节点被访问的次数
vector<int> count(n, 0);
for (const auto& trip : trips) {
int start = trip[0], end = trip[1];
// 使用DFS或BFS找到路径并统计节点访问次数
vector<int> parent(n, -1);
queue<int> q;
q.push(start);
parent[start] = start;
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == end) break;
for (int v : tree[u]) {
if (parent[v] == -1) {
parent[v] = u;
q.push(v);
}
}
}
// 回溯路径并统计节点访问次数
int node = end;
while (node != start) {
count[node]++;
node = parent[node];
}
count[start]++;
}
// 动态规划求解最优减半策略
// dp[u][0]表示u不减半，dp[u][1]表示u减半
vector<vector<int>> dp(n, vector<int>(2, -1));
function<int(int, int, bool)> dfs = [&](int u, int parent, bool canHalve) {
if (dp[u][canHalve] != -1) return dp[u][canHalve];
int notHalve = price[u] * count[u];
int halve = (price[u] / 2) * count[u];
for (int v : tree[u]) {
if (v == parent) continue;
notHalve += dfs(v, u, true);
if (canHalve) {
halve += dfs(v, u, false);
}
}
if (!canHalve) {
dp[u][0] = notHalve;
return notHalve;
} else {
dp[u][1] = min(notHalve, halve);
return dp[u][1];
}
};
return dfs(0, -1, true);
}
};五、总结
本题巧妙结合图论路径统计与动态规划。通过邻接表构建树降低复杂度，利用BFS遍历路径并回溯统计访问次数，动态规划中通过状态定义优化决策过程。关键突破在于“减半策略仅对当前节点生效”，需严格传递状态避免重复计算。该解法时间复杂度为O(N+M)，空间复杂度为O(N)，适用于树形结构优化问题
原创内容 转载请注明出处
