Leetcode 2646. 最小化旅行的价格总和（暴力 DFS + 树形 DP）

本文主要是介绍Leetcode 2646. 最小化旅行的价格总和（暴力 DFS + 树形 DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 2646. 最小化旅行的价格总和（暴力 DFS + 树形 DP）
题目
- 现有一棵无向、无根的树，树中有 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 <= 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：
- 第 1 步：
- 思考在不折半的情况下，每次旅行的最小值：start 到 end 的最短路径（不走回头路）
- 第 2 步：
- 先建树，然后枚举 trips 计算每次 start 到 end 的最短路径
- 找到该路径所有点，求出每个点使用次数 * 价格
- 此时问题转化为：每个点的价格固定（次数 * 价格），求非相邻节点后、所有节点总和的最小值
- 第 3 步：
- 类似：337. 打家劫舍 III
- 树形 DP
- dp[i][j] 代表 i 子树处、所有旅行的最小价格总和，j=0-不折半，j=1-i折半
- 动规转移方程：
  - dp[i][0] = min(dp[child][0]，dp[child][1]) + pointPrice[i]：i 不折半则 i 的孩子可以折半也可以不折半
  - dp[i][1] = dp[child][0] + pointPrice[i]/2：i 折半则 i 的孩子一定不折半
- 时间复杂度：O（n * m），空间复杂度：O（n）
代码

/*** 暴力 DFS + 树形 DP：** 第 1 步：* 思考在不折半的情况下，每次旅行的最小值：start 到 end 的最短路径（不走回头路）** 第 2 步：* 先建树，然后枚举 trips 计算每次 start 到 end 的最短路径* 找到该路径所有点，求出每个点使用 次数 * 价格* 此时问题转化为：每个点的价格固定（次数 * 价格），求 非相邻节点 后、所有节点总和的最小值** 第 3 步：* 类似：337. 打家劫舍 III* 树形 DP* dp[i][j] 代表 i 子树处、所有旅行的最小价格总和，j=0-不折半，j=1-i折半* 动规转移方程：*     * dp[i][0] = min(dp[child][0]，dp[child][1]) + pointPrice[i]，i 不折半则 i 的孩子可以折半也可以不折半，*     * dp[i][1] = dp[child][0] + pointPrice[i]/2，i 折半则 i 的孩子一定不折半，* 时间复杂度：O（n * m），空间复杂度：O（n）*/public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {// 建树List<Integer>[] treeList = buildTree(n, edges);// 每个点使用次数 * 价格int[] pointPrice = new int[n];// 枚举 trips 计算每次 start 到 end 的最短路径（不走回头路）List<Integer> pointList = new ArrayList<>();for (int[] trip : trips) {int start = trip[0];int end = trip[1];pointList.clear();pointList.add(-1);dfsShortestPath(start, -1, treeList, end, pointList);// 求出每个点使用次数 * 价格for (int i = 1; i < pointList.size(); i++) {int point = pointList.get(i);pointPrice[point] += price[point];}}// dp[i][j] 代表 i 子树处、所有旅行的最小价格总和，j=0-不折半，j=1-i折半int[][] dp = new int[n][2];dfsMinPrice(0, -1, treeList, pointPrice, dp);return Math.min(dp[0][0], dp[0][1]);}/*** dp[i][j] 代表 i 子树处、所有旅行的最小价格总和，j=0-不折半，j=1-i折半*/private void dfsMinPrice(int son, int father, List<Integer>[] treeList, int[] pointPrice, int[][] dp) {int nextNot = 0;int nextMin = 0;for (int next : treeList[son]) {if (next != father) {dfsMinPrice(next, son, treeList, pointPrice, dp);nextNot += dp[next][0];nextMin += Math.min(dp[next][0], dp[next][1]);}}dp[son][0] = nextMin + pointPrice[son];dp[son][1] = nextNot + (pointPrice[son] >> 1);}/*** 计算每次 start 到 end 的最短路径（不走回头路）* 返回路径上所有的点*/private void dfsShortestPath(int son, int father, List<Integer>[] treeList, int end, List<Integer> pointList) {if (son == end) {pointList.add(son);return;}for (int next : treeList[son]) {if (next != father) {pointList.add(son);dfsShortestPath(next, son, treeList, end, pointList);// 遍历到 end 节点，不用清理只直接退出if (pointList.get(pointList.size() - 1) == end) {return;}pointList.remove(pointList.size() - 1);}}}/*** 建树*/private List<Integer>[] buildTree(int n, int[][] edges) {List<Integer>[] edgeList = new ArrayList[n];for (int i = 0; i < n; i++) {edgeList[i] = new ArrayList<>();}for (int i = 0; i < edges.length; i++) {int u = edges[i][0];int v = edges[i][1];edgeList[u].add(v);edgeList[v].add(u);}return edgeList;}