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) 代码
public int minimumTotalPrice ( int n, int [ ] [ ] edges, int [ ] price, int [ ] [ ] trips) {
List < Integer > [ ] treeList = buildTree ( n, edges) ;
int [ ] pointPrice = new int [ n] ;
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] ;
}
}
int [ ] [ ] dp = new int [ n] [ 2 ] ;
dfsMinPrice ( 0 , - 1 , treeList, pointPrice, dp) ;
return Math . min ( dp[ 0 ] [ 0 ] , dp[ 0 ] [ 1 ] ) ;
}
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 ) ;
}
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) ;
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;
}