【每日一题】最小化旅行的价格总和

文章目录

Tag
题目来源
题目解读
解题思路
- 方法一：深搜+动态规划
写在最后

Tag

【深搜+动态规划】【树】【2023-12-06】

题目来源

2646. 最小化旅行的价格总和

题目解读

有一棵无向、无根的树，树中的节点从 0 到 n-1，每个节点有一个关联的价格，你可以把不相邻节点的关联价格减半，现在要从一些节点到另一些节点称为旅行（各自独立的），返回执行所有旅行的最小代价总和。

解题思路

一开始的想法是这样的，如果没有「减半」操作，那这道题目就是最短路径问题。但是有了「减半」就无从下手了。

方法一：深搜+动态规划

思路

为了使旅行的价格总和最小，每次旅行的路径必须是最短路径。因此，我们每次从旅行的起点 trip[i][0] 出发，需要「朝向」终点 trip[i][1] 前进，这个「朝向」我们用一个深搜（递归）来实现。

在深搜过程中我们将经过节点的次数记录下来，后续就可以根据经过节点的次数来计算旅行的价格。并且，这样可以方便后续的「减半」操作。

题目中说的「选择一些 非相邻节点 并将价格减半」，换言之，如果一个节点减半了，那么其下一个节点（子节点或者父节点）不能减半，如果一个节点没有减半，那么其下一个节点（子节点或者父节点）可以减半。在这样的情况下，计算最小旅行价格。

本节点的选择可能会影响到相邻节点的选择，这不就是动态规划问题吗？相应的题目为 337. 打家劫舍 III。

在打家劫舍问题中，给出的是一棵二叉树，可以从根节点开始进行动态规划，本题是一个无向图，可以随意选择一个节点作为根节点进行动态规划。我们选择从节点 0 出发在树上进行动态规划，对于节点 x 及其儿子 y 需要分类讨论：

如果 prices[x] 不变，那么 prices[y] 可以减半，也可以不减半，取二者最小值；
如果 prices[x] 减半，那么 prices[y] 只能不变。

因此，子树 x 需要返回两个值：

prices[x] 不变时的子树 x 的最小代价总和；
prices[x] 减半时的子树 x 的最小代价总和。

最终的答案就是，以 0 作为根节点，减半或者不减半时的最小旅行价格。

算法

在具体实现中：

首先，建立无向图；
接着，递归更新记录节点次数的数组；
然后，在树上进行动态规划；
最后，返回以 0 为根的最小旅行代价。

class Solution {
public:
    int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
        vector<vector<int>> g(n);
        // 建树
        for (auto edge : edges) {
            int x= edge[0], y = edge[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        vector<int> cnts(n);    // 存放节点的次数
        function<bool(int, int, int)> dfs = [&](int x, int pa, int end)->bool {
            if (x == end) {
                cnts[x] += 1;
                return true;
            }

            for (int y : g[x]) {
                if (y != pa && dfs(y, x, end)) {
                    cnts[x] += 1; // x 是朝向 end 前进的，记录
                    return true;
                }
            }
            return false;
        };
        for (auto& trip : trips) {
            dfs(trip[0], -1, trip[1]);
        }

        // 打家劫舍 III
        function<pair<int, int>(int, int)> dp = [&](int x, int pa) -> pair<int, int> {
            int not_halve = price[x] * cnts[x];     // x 不变
            int halve = not_halve / 2;              // x 减半

            for (int y : g[x]) {
                if (y != pa) {
                    auto [nh, h] = dp(y, x);        // y 不变与 y 减半
                    not_halve += min(nh, h);        // x 不变，y 取不变与变中的较小值
                    halve += nh;                    // x 减半，y 只能不变
                }
            }
            return {not_halve, halve};
        };
        
        auto [nh, h] = dp(0, -1);
        return min(nh, h);
    }
};