题解 | #牛妹的野菜（权值最大的路径）#

思路：

题目的主要信息：

一个有向无环图，路径是单向从小序号到大序号，每个节点有权值
求图中一条权值和最大的路径，并以字符串输出这条路径

方法一：动态规划
具体做法：
我们可以用动态规划的方式来解决。
首先利用给出的路径数组构建一个邻接矩阵，我们以weigh数组表示从每个节点开始的最长路径的长度，path表示这条路径的字符串组成，初始时都只有自己。因为是从每个节点开始的最长路径的长度，为了方便“-”的连接，我们逆序查找。每到一个节点，我们遍历其所有直接相连的后续节点，找到最长的路径，将其放入上述两个数组。但是因为这种连接会断，因此第一个并非一定是最大，因此我们还需要遍历weigh数组找到最大值及最大路径的字符串组成。
图片说明

class Solution {
public:
    string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) {
        int n = potatoNum.size();
        string res = "";
        vector<vector<int> > G(n + 1);
        for(int i = 0; i < connectRoad.size(); i++) //邻接矩阵
            G[connectRoad[i][0]].push_back(connectRoad[i][1]);
        vector<int> weigh(n + 1, 0); //记录以某个节点为起点的总权重
        vector<string> path(n + 1, ""); //记录以某个节点为起点的总路径
        for(int i = n; i >= 1; i--){
            weigh[i] = potatoNum[i - 1]; //最开始权重就是该节点
            path[i] = to_string(i); //最开始路径就是该节点
            int max = 0;
            int id = 0;
            for(int j = 0; j < G[i].size(); j++){ //遍历其可以过去的所有路径
                if(weigh[G[i][j]] > max){ //找到最大总权值
                    max = weigh[G[i][j]];
                    id = G[i][j];
                }
            }
            if(max){ //如果找到了最大值，将其接在后面
                weigh[i] += max;
                path[i] += "-" + path[id];
            }
        }
        int maxweigh = 0;
        for(int i = 1; i <= n; i++){ //遍历找到最大权重路径
            if(maxweigh < weigh[i]){
                maxweigh = weigh[i];
                res = path[i];
            }
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n+m)$ ，其中 $n$ 为数组potatoNum的长度， $m$ 为数组connectRoad的长度。主体循环外循环 $n$ 次，但是内循环遍历所有的路径矩阵，总共只有 $m$ 次，而主体循环外也刚好是 $O(n+m)$
空间复杂度： $O(n^2)$ ，最坏情况下邻接矩阵为边长是 $n$ 的二维矩阵

方法二：空间记忆搜索（dfs)
具体做法：
方法一的动态规划我们可以改成一个递归，即用dfs正向搜索相加，但是复杂度过大，重复计算很多，我们可以用数组来记忆递归过程中的中间值，这样就省略了很多计算。
我们以weigh数组表示从每个节点结束的最长路径的长度，path表示这条路径的字符串组成，这样我们可以正向搜索，dfs向下找到最大权值路径。同时要在当前记录权值weigh[i]小于当前结点的权值时再dfs更新，否则可以直接食用weigh中的值，同时dfs过程中也要优先使用weigh数组中的值，只有其更小时才会更新。

class Solution {
public:
    //深度优先搜索，往下找到最大连接路径
    void dfs(int v, vector<int>& potatoNum, vector<vector<int>>& G, vector<int>& weigh, vector<string>& path){
        for(int i = 0; i < G[v].size(); i++){
            if(weigh[G[v][i]] < weigh[v] + potatoNum[G[v][i] - 1]){
                weigh[G[v][i]] = weigh[v] + potatoNum[G[v][i] - 1]; //权值更新
                path[G[v][i]] = path[v] + "-" + to_string(G[v][i]); //路径连接
                dfs(G[v][i], potatoNum, G, weigh, path);
            }
        }
    }
    string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) {
        int n = potatoNum.size();
        string res = "";
        vector<vector<int> > G(n + 1);
        for(int i = 0; i < connectRoad.size(); i++) //邻接矩阵
            G[connectRoad[i][0]].push_back(connectRoad[i][1]);
        vector<int> weigh(n + 1, 0); //记录以某个节点为终点的总权重
        vector<string> path(n + 1, ""); //记录以某个节点为终点的总路径
        for(int i = 1; i <= n; i++){ //正向搜索
            if(weigh[i] < potatoNum[i - 1]){  //只有当权值小于这个数时才更新
                weigh[i] = potatoNum[i - 1];
                path[i] = to_string(i);
                dfs(i, potatoNum, G, weigh, path);
            }
        }
        int maxweigh = 0;
        for(int i = 1; i <= n; i++){ //遍历找到最大权重路径
            if(maxweigh < weigh[i]){
                maxweigh = weigh[i];
                res = path[i];
            }
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n+m)$ ，其中 $n$ 为数组potatoNum的长度， $m$ 为数组connectRoad的长度。主体循环外循环最坏情况下 $n$ 次，里面的递归是遍历所有的路径矩阵，总共只有 $m$ 次，而主体循环外也刚好是 $O(n+m)$
空间复杂度： $O(n^2+m)$ ，最坏情况下邻接矩阵为边长是 $n$ 的二维矩阵，以及递归栈最大深度为 $m$ ，其中 $m$ 和 $n$ 的大小关系未知，不可轻易省略低次幂