题解 | #权值最大的路径#

题目：
给出一个有向无环图，规定路径是单向且小序号指向大序号，每个节点都有权值。在图上求一条路径使得经过的节点权值和最大，输出路径
方法一：递归

• 先构建邻接矩阵存储每个结点的邻接结点
• 记录以每个结点为结尾结点时的路径权值和以及路径，路径权值和存储在w数组中，对应路径存储在path数组中，找出路径权值和最大的结点所对应的路径数组
• 如果以当前结点为结尾的路径权值和小于该结点原本的权值时递归更新路径，在递归中，遍历当前结点的邻接结点，如果邻接结点的权值小于当前结点权值加上邻接结点权值，则更新邻接结点的权值，并且更新路径数组，继续递归，递归结束条件为结已经没有邻接结点了

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param potatoNum int一维数组 依次表示序号为1,2,3..的节点的权值
     * @param connectRoad int二维数组 每个一维数组[x,y]表示从第x号到第y号有路
     * @return string
     */
    int max=0;
    int[]w;//记录以每个结点为结尾的路径权值和
    String[]path;//记录以每个结点为结尾的路径
    public String digSum (int[] potatoNum, int[][] connectRoad) {
        // write code here
        int n=potatoNum.length;
        w=new int[n+1];
        path=new String[n+1];
        ArrayList<ArrayList<Integer>>G=new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<=n;i++)G.add(new ArrayList<Integer>());
        for(int i=0;i<connectRoad.length;i++){
            G.get(connectRoad[i][0]).add(connectRoad[i][1]);//建立邻接矩阵
        }
        for(int i=1;i<=n;i++){
            if(w[i]<potatoNum[i-1]){//如果以当前结点为结尾的路径权值和小于原本的权值时递归更新路径
                w[i]=potatoNum[i-1];
                path[i]=String.valueOf(i);
                dfs(i,potatoNum,G);
            }
        }
        String res="";
        for(int i=1;i<=n;i++){//找出路径权值和最大的结点所对应的路径数组
            if(max<w[i]){
                max=w[i];
                res=path[i];
            }
        }
        return res;
    }
    void dfs(int v,int[]potatoNum,ArrayList<ArrayList<Integer>>G){
       for(int i=0;i<(G.get(v)).size();i++){//访问结点的邻接结点，递归结束条件为当结点没有邻接结点
           if(w[(G.get(v)).get(i)]<w[v]+potatoNum[(G.get(v)).get(i)-1]){//如果邻接结点权值小于当前结点的权值加上邻接结点的权值
               w[(G.get(v)).get(i)]=w[v]+potatoNum[(G.get(v)).get(i)-1];//更新邻接结点的权值
               path[(G.get(v)).get(i)]=path[v]+"-"+String.valueOf((G.get(v)).get(i));//更新以邻接结点为结尾结点的路径
               dfs((G.get(v)).get(i),potatoNum,G);//继续寻找下一个邻接结点
           }
       }
    }
}

复杂度：
时间复杂度：,递归复杂度不超过
空间复杂度：,图的大小不超过mn
(m为connectRoad的长度，n为potatoNum的长度)
方法二：递推
也可以采用递推解决问题：

• 从后往前遍历结点，将路径数组path初始化为本身，权值数组初始化为原先结点的权值
• 寻找权值最大的邻接结点接到当前结点的后面
• 最后找出权值最大结点所对应的路径
  比如：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param potatoNum int一维数组 依次表示序号为1,2,3..的节点的权值
     * @param connectRoad int二维数组 每个一维数组[x,y]表示从第x号到第y号有路
     * @return string
     */
    int max=0;
    int[]w;//记录以每个结点为结尾的路径权值和
    String[]path;//记录以每个结点为结尾的路径
    public String digSum (int[] potatoNum, int[][] connectRoad) {
        // write code here
        int n=potatoNum.length;
        w=new int[n+1];
        path=new String[n+1];
        ArrayList<ArrayList<Integer>>G=new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<=n;i++)G.add(new ArrayList<Integer>());
        for(int i=0;i<connectRoad.length;i++){
            G.get(connectRoad[i][0]).add(connectRoad[i][1]);//建立邻接矩阵
        }
        for(int i=n;i>=1;i--){//从后往前递推，每次都找到当前结点的权值最大邻接结点，把该结点路径接到当前结点路径后面
            w[i]=potatoNum[i-1];
            path[i]=String.valueOf(i);//路径先初始化为只有该结点
            int max=0;
            int index=0;
            for(int j=0;j<(G.get(i)).size();j++){
                if(w[(G.get(i)).get(j)]>max){
                    max=w[(G.get(i)).get(j)];
                    index=(G.get(i)).get(j);
                }
            }
            if(max!=0)
            {w[i]+=max;
             path[i]+="-"+path[index];}
        }
        //找到权值和最大结点对应的路径
        String res="";
        for(int i=1;i<=n;i++){
            if(max<w[i]){
                max=w[i];
                res=path[i];
            }
        }
        return res;
    }
}

复杂度：
时间复杂度：,内层循环遍历次数不超过m，总的平均时间复杂度为
空间复杂度：，矩阵大小不超过mn
(m为connectRoad的长度，n为potatoNum的长度)