目录
2646. 最小化旅行的价格总和
题目描述:
实现代码与解析:
DFS + DP
原理思路:
2646. 最小化旅行的价格总和
题目描述:
现有一棵无向、无根的树,树中有 n
个节点,按从 0
到 n - 1
编号。给你一个整数 n
和一个长度为 n - 1
的二维整数数组 edges
,其中 edges[i] = [ai, bi]
表示树中节点 ai
和 bi
之间存在一条边。
每个节点都关联一个价格。给你一个整数数组 price
,其中 price[i]
是第 i
个节点的价格。
给定路径的 价格总和 是该路径上所有节点的价格之和。
另给你一个二维整数数组 trips
,其中 trips[i] = [starti, endi]
表示您从节点 starti
开始第 i
次旅行,并通过任何你喜欢的路径前往节点 endi
。
在执行第一次旅行之前,你可以选择一些 非相邻节点 并将价格减半。
返回执行所有旅行的最小价格总和。
示例 1:
输入:n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]] 输出:23 解释: 上图表示将节点 2 视为根之后的树结构。第一个图表示初始树,第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。 第 1 次旅行,选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。 第 2 次旅行,选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。 第 3 次旅行,选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。 所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明,23 是可以实现的最小答案。
示例 2:
输入:n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]] 输出:1 解释: 上图表示将节点 0 视为根之后的树结构。第一个图表示初始树,第二个图表示选择节点 0 并使其价格减半后的树。 第 1 次旅行,选择路径 [0] 。路径的价格总和为 1 。 所有旅行的价格总和为 1 。可以证明,1 是可以实现的最小答案。
提示:
1 <= n <= 50
edges.length == n - 1
0 <= ai, bi <= n - 1
edges
表示一棵有效的树price.length == n
price[i]
是一个偶数1 <= price[i] <= 1000
1 <= trips.length <= 100
0 <= starti, endi <= n - 1
实现代码与解析:
DFS + DP
C++
class Solution {
public:
int N = 50 + 10;
vector<int> e = vector<int>(N * 2, 0), ne = vector<int>(N * 2, 0), h = vector<int>(N, -1);
vector<int> cnt = vector<int>(N, 0);
int idx= 0;
// 邻接表加边
void add(int a, int b) {
e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
bool dfs(int cur, int p, int end) {
if (cur == end) {
cnt[cur]++;
return true;
}
for (int i = h[cur]; ~i; i = ne[i]) {
int j = e[i];
if (j == p) continue;
if (dfs(j, cur, end)) {
cnt[cur]++;
return true;
}
}
return false;
}
// first,当前节点不减半可以获得的最小金额,second,当前节点减半
pair<int, int> dpf(int cur, int p, vector<int> price) {
pair<int, int> res = {price[cur] * cnt[cur], price[cur] * cnt[cur] / 2};
for (int i = h[cur]; ~i; i = ne[i]) {
int j = e[i];
if (j == p) continue;
pair<int, int> t = dpf(j, cur, price);
res.first += min(t.first, t.second); // 当前节点不减半,那么孩子可减半,也可不减取最大
res.second += t.first; // 当前节点减半,子节点一定不能减半
}
return res;
}
int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
// 初始化图
for (auto e: edges) {
add(e[0], e[1]);
add(e[1], e[0]);
}
// dfs
for (auto t: trips) {
dfs(t[0], -1, t[1]);
}
auto [x, y] = dpf(0, -1, price);
return min(x, y); // 取最小
}
};
Java
class Solution {
public int N = 50 + 10;
public int[] e = new int[N * 2], ne = new int[N * 2], h = new int[N];
public int[] cnt = new int[N];
public int idx = 0;
public void add(int a, int b) {
e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
public boolean dfs(int cur, int p, int end) {
if (cur == end) {
cnt[cur]++;
return true;
}
for (int i = h[cur]; i != -1; i = ne[i]) {
int j = e[i];
if (j == p) continue;
if (dfs(j, cur, end)) {
cnt[cur]++;
return true;
}
}
return false;
}
public int[] dp(int cur, int p, int[] price) {
int[] res = {price[cur] * cnt[cur], price[cur] * cnt[cur] / 2};
for (int i = h[cur]; i != -1; i = ne[i]) {
int j = e[i];
if (j == p) continue;
int[] t = dp(j, cur, price);
res[0] += Math.min(t[0], t[1]);
res[1] += t[0];
}
return res;
}
public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
Arrays.fill(h, -1);
for (int[] t: edges) {
add(t[0], t[1]);
add(t[1], t[0]);
}
for (int[] t: trips) {
dfs(t[0], -1, t[1]);
}
int[] res = dp(0, -1, price);
return Math.min(res[0], res[1]);
}
}
原理思路:
此题,可以拆分为两道题,DFS + 树形DP。
dp之前先用dfs遍历处理一下,找出每个节点总共经过的次数。
dp返回数组的含义和递推式:
res[0]表示,此节点不减半可获得的最小值,此节点不减半,那么其孩子节点就可减半,可不减半,取最小min。res[0] += min(childres[0], childres[1]); // 这里用childres来表示孩子返回值解释
res[1]表示,此节点减半可获取的最小值,此节点减半,那么其孩子节点就一定不能减半,直接加上孩子返回的不减半值即可。 res[1] += childres[0];
和树形的 打家劫舍III 思路相同,只不过那题是取最大值。
Leetcode每日一题:打家劫舍系列Ⅰ、Ⅱ、Ⅲ、Ⅳ(2023.9.16~2023.9.19 C++)_Cosmoshhhyyy的博客-CSDN博客