2646. 最小化旅行的价格总和 (opens new window)

1.深搜+树形dp

1、深搜：首先需要统计每次旅行中，经过的节点次数。因为是无根树，所以每次旅行的路径都是唯一的。

2、动态规划：每个节点上的总价值=节点经过的次数 x 当前节点的价值。节点如果一次没经过，则置为0。因此节点价值减半等效于节点的总价值减半，题目转化为打家劫舍Ⅲ场景的树形dp。

需要维护一个cache哈希表，记录当前节点不同状态下作为根所能得到的最小金额数量。

class Solution {
    Map<String, Integer> cache = new HashMap<>();
    public  int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < edges.length; i++) {
            g[edges[i][0]].add(edges[i][1]);
            g[edges[i][1]].add(edges[i][0]);
        }
        int[] count = new int[n];
        //1.找出每条路径的经过的所有点数
        for (int i = 0; i < trips.length; i++) {
            boolean ans=dfs(g,count, -1,trips[i][0], trips[i][1]);
        }
        //2.动规求解路径减半
        for (int i = 0; i < count.length; i++) {
            count[i] = count[i] * price[i];
        }
        int res1=dp(g, count, -1,0, 1);
        int res2=dp(g, count, -1,0, -1);
        return Math.min(res1, res2);
    }
    private int dp(List<Integer>[] g, int[] count, int pre,int curr, int redu) {
        //redu:1表示当前节点减半 -1表示当前节点不减半
        int sum = redu==1?count[curr]/2:count[curr];
        String currKey = String.valueOf(curr) + "&" + String.valueOf(redu);
        for (Integer next : g[curr]) {
            String key1 = String.valueOf(next) + "&" + String.valueOf(1);
            String key2 = String.valueOf(next) + "&" + String.valueOf(-1);
            if (next != pre) {
                if (redu == 1) {
                    int tmp2 = cache.containsKey(key2) ? cache.get(key2) : dp(g, count, curr, next, -1);
                    sum+=tmp2;
                    cache.put(key2, tmp2);
                }
                else{
                    int tmp1 = cache.containsKey(key1) ? cache.get(key1) : dp(g, count, curr, next, 1);
                    int tmp2 = cache.containsKey(key2) ? cache.get(key2) : dp(g, count, curr, next, -1);
                    sum += Math.min(tmp1,tmp2);
                    cache.put(key1, tmp1);
                    cache.put(key2, tmp2);
                }
            }
        }
        cache.put(currKey, sum);
        return sum;
    }

    private boolean dfs(List<Integer>[] g, int[] count, int pre, int node, int target) {
        if (node == target) {
            count[target]++;
            return true;
        }
        boolean check = false;
        for (Integer next : g[node]) {
            if (next != pre) {
                boolean res = dfs(g, count, node, next, target);
                if(res) check = true;
            }
        }
        if (check) {
            count[node]++;
            return true;
        }
        return false;
    }
}