权值最大的路径

class Solution {
public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 
   * @param potatoNum intvector 依次表示序号为1,2,3..的节点的权值
   * @param connectRoad intvector<vector<>> 每个一维数组[x,y]表示从第x号到第y号有路
   * @return string
   */
  string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) {
    const int n = potatoNum.size();
    vector<vector<int>> g(n + 1);
    for (const auto& c : connectRoad)
      g[c[0]].emplace_back(c[1]);
    
    function<pair<int, string>(int)> dfs = [&](int u) {
      if (memo_.find(u) != end(memo_))
        return memo_.at(u);
      
      if (g[u].empty()) // leaf node case
        return memo_[u] = make_pair(potatoNum[u - 1], to_string(u));
      
      string path;
      int weight = 0;
      for (const int nxt : g[u]) {
        auto [w, p] = dfs(nxt);
        if (w > weight) {
          path = p;
          weight = w;
        }
      }
      
      return memo_[u] = make_pair(potatoNum[u - 1] + weight, to_string(u) + '-' + path);
    };
    
    string ans;
    int weight = 0;
    for (int u = 1; u <= n; ++u) {
      const auto [w, path] = dfs(u);
      if (w > weight) {
        weight = w;
        ans = path;
      }
    }
    
    return ans;
  }
  
private:
  unordered_map<int, pair<int, string>> memo_;
};

class Solution {
public:
    /**
     * 
     * @param potatoNum int整型vector 依次表示序号为1,2,3..的番薯洞各有多少个番薯
     * @param connectRoad int整型vector<vector<>> 每个一维数组[x,y]表示从第x号番薯洞到第y号有路
     * @return string字符串
     */
    string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) {
        // write code here
        int sz = potatoNum.size();
        vector<vector<int> > path(sz +1);    // 存路径，从后往前存
        for(auto e: connectRoad){
            path[e[1]].push_back(e[0]);
        }
        vector<pair<int,int>> dp(sz+1);    // 每个节点  可摘取的最大数量，以及路径的前一个节点
        dp[0] = {0,0};
        for(int i=1;i<sz+1;i++){
            pair<int,int> Maxtemp = {0,0};
            for(int j=0;j<path[i].size();j++){
                if(dp[path[i][j]].first > Maxtemp.first){
                    Maxtemp.first = dp[path[i][j]].first;
                    Maxtemp.second = path[i][j];
                }
            }
            dp[i] = {Maxtemp.first+potatoNum[i-1],Maxtemp.second};
        }
        
        int maxnum = 0;    //最大可采摘数量
        int maxindex = 0;    // 最大可采摘数量对应的节点
        for(int i = 0;i<sz+1;i++){
            if(dp[i].first>maxnum){
                maxnum = dp[i].first;
                maxindex = i;
            }
        }
        
        vector<int> resint; 
        
        while(maxindex!=0){
            resint.push_back(maxindex);
            maxindex = dp[maxindex].second;
        }
        
        string res;
        for(int i =resint.size()-1;i>=0;i--){
            string s = to_string(resint[i]);
            res.append(s);
            if(i!=0){
                res.append("-");
            }  
        }
        return res;
    }
};

//该方法遍历深度较大，所以只过了80%，剩下的超时了，实在想不出哪里可以剪枝
//望大佬提供一下剪枝四路
class Solution {
public:
    void find(vector<int>& potatoNum, vector<vector<int> >& connectRoad,int i,int tmp)
    {
        tmp+=potatoNum[i - 1];//累加到达当前洞口中的番茄个数
        part.push_back(i);//存入当前路劲
                //循环遍历找当前洞口联通的下一个洞口
        for(int k = 0;k<connectRoad.size();k++)
        {
            if(connectRoad[k][0] == i)//找到了
                find(potatoNum,connectRoad,connectRoad[k][1],tmp);//进入该洞口
        }
                //当走到这里时，表示到达了当前路劲的尽头，判断当前路劲下取得番茄个数是否大于
                //max，如果大于，则番茄个数交换，最佳路径交换
        if(tmp > max)
        {
          best_part = part;
          max = tmp;
        }
                //当前路劲返回上一层，继续寻找下一个联通的洞穴
        part.pop_back();
    }
    string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) {
        // write code here
                //分别从每个洞口开始找
        for(int i = 1;i<potatoNum.size() + 1;i++)
        {
            find(potatoNum,connectRoad,i,0);
        }
                //以下是返回string
        string str("");
        for(int i = 0;i<best_part.size();i++)
        {
            int tmp = best_part[i];
            stringstream ss;
            ss<<tmp;
            str+=ss.str();
            if(i != best_part.size() - 1)
                str+="-";
        }
        return str;
    }
public:
    vector<int> part;//当前路径
    vector<int> best_part;//取得最多番茄个数的路径
    int max = 0;//番茄最多个数
};