题目

给定一个表示番薯洞的地图，每个番薯洞中有一定数量的番薯。
已知番薯洞的连接路径，并规定路径是单向且小序号指向大序号，也无环。
可以从任意一处开始挖，然后沿着连接往下挖（仅能选择一条路径），当无连接时，结束。
设计一种挖番薯的方案，使得可以挖到更多的番薯。
输出路径。

方法一 深度优先搜索（超时）

使用 记录每个节点可以指向的节点。
从 1 到 n 遍历每个节点，使用 DFS 从该节点开始访问连接指向的所有细胞。在搜索期间更新番薯的最大数量，并更新路径。
在搜索完成后返回答案。
用 记录节点是否有前驱节点。

C++代码

class Solution {
    vector<vector<int>> next;
    vector<bool> vis;
    int maxCnt;
    string maxPath;

    void dfs(int a, int cnt, string path, vector<int>& potatoNum){
        for(int i=0; i<next[a].size(); ++i){
            int b = next[a][i];
            vis[b] = true;
            int itmp = cnt + potatoNum[b-1];
            string stmp = path + "-" + to_string(b);
            if(itmp > maxCnt){
                maxCnt = itmp;
                maxPath = stmp;
            }
            dfs(b, itmp, stmp, potatoNum);
        }
    }
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 n = potatoNum.size();
        next.resize(n+1);
        for(auto &r : connectRoad){
            next[r[0]].push_back(r[1]);
        }
        maxCnt = 0;
        vis.resize(n+1, false);
        for(int i=1; i<=n; ++i){
            if(vis[i])
                continue;
            int cnt = potatoNum[i-1];
            string path = to_string(i);
            if(cnt > maxCnt){
                maxCnt = cnt;
                maxPath = path;
            }
            dfs(i, cnt, path, potatoNum);
        }

        return maxPath;
    }
};

方法二 动态规划

方法一有很多重复的计算。
例如：

[5,10,20,5,4,5],[[1,2],[1,4],[2,4],[3,4],[4,5],[4,6],[5,6]]

在节点 1 中计算了 1-2-4-5-6，在节点 3 中计算了 3-4-5-6，重复计算了路径 4-5-6。

为了防止这些重复计算，换一下思路，从 n 到 1 遍历节点。

表示从节点 开始到无连接时的最大番薯数目：取节点 的后继节点的最大值，再加上节点 本身的值。
状态转移方程：。 记录每个节点的后继节点。
最后，遍历所有节点，返回其最大值对应的路径。

C++代码

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 n = potatoNum.size();
        vector<vector<int>> next(n+1);
        for(auto &r : connectRoad){
            next[r[0]].push_back(r[1]);
        }

        vector<int> cnt(n+1, 0);
        vector<string> path(n+1, "");
        for(int i=n; i>=1; --i){
            cnt[i] = potatoNum[i-1];
            path[i] = to_string(i);

            int tmp = 0;
            int e = 0;
            for(int j=0; j<next[i].size(); ++j){
                int b = next[i][j];
                if(cnt[b] > tmp){
                    tmp = cnt[b];
                    e = b;
                }
            }
            if(tmp){
                cnt[i] += tmp;
                path[i] += "-" + path[e];
            }
        }

        int maxCnt = 0;
        string maxPath = "";
        for(int i=1; i<=n; ++i){
            if(cnt[i] > maxCnt){
                maxCnt = cnt[i];
                maxPath = path[i];
            }
        }
        return maxPath;
    }
};

方法三 记忆化深度优先搜索

记忆化深度优先搜索与朴素深度优先搜索的区别：前者使用缓存存储了节点的数据，这样可以不用多次重复计算同一个节点。

此处的 与方法二中的意思不同，表示以节点 为结尾的路径中的最大番薯数目。

函数 中有一个判断条件 ，这表示这条路径还有进行延伸的价值，更新 。

C++代码

class Solution {
    vector<vector<int>> next;
    vector<int> cnt;
    vector<string> path;

    void dfs(int a, vector<int>& potatoNum){
        for(int i=0; i<next[a].size(); ++i){
            int b = next[a][i];
            if(cnt[b] < cnt[a] + potatoNum[b-1]){
                cnt[b] = cnt[a] + potatoNum[b-1];
                path[b] = path[a] + "-" + to_string(b);
                dfs(b, potatoNum);
            }
        }
    }
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 n = potatoNum.size();
        next.resize(n+1);
        for(auto &r : connectRoad){
            next[r[0]].push_back(r[1]);
        }
        cnt.resize(n+1, 0);
        path.resize(n+1, "");

        for(int i=1; i<=n; ++i){
            if(cnt[i] < potatoNum[i-1]){
                cnt[i] = potatoNum[i-1];
                path[i] = to_string(i);
                dfs(i, potatoNum);
            }
        }

        int maxCnt = 0;
        string maxPath = "";
        for(int i=1; i<=n; ++i){
            if(cnt[i] > maxCnt){
                maxCnt = cnt[i];
                maxPath = path[i];
            }
        }
        return maxPath;
    }
};