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

题意整理

给定一个有向无环图，每个节点都有一个权值。
求所有路径中，节点权值和最大的路径。

方法一（记忆化递归）

1.解题思路

递归终止条件：跟新完所有的节点。
递归如何推进：每跟新完一个后置节点，就将当前后置节点作为新的起点进行递归。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param potatoNum int一维数组 依次表示序号为1,2,3..的节点的权值
     * @param connectRoad int二维数组 每个一维数组[x,y]表示从第x号到第y号有路
     * @return string
     */
    int n;
    //权值数组
    int[] w;
    //路径数组
    String[] path;
    int[] potatoNum;
    //邻接矩阵
    int[][] graph;

    public String digSum (int[] potatoNum, int[][] connectRoad) {
        //初始化
        this.n=potatoNum.length;
        this.w=new int[n+1];
        this.path=new String[n+1];
        this.potatoNum=potatoNum;
        this.graph=new int[n+1][n+1];

        //给邻接矩阵赋值
        for(int[] road:connectRoad){
            graph[road[0]][road[1]]=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);
            }
        }
        int max=0;
        String res="";
        //求最大权值对应的路径
        for(int i=1;i<=n;i++){
            if(max<w[i]){
                max=w[i];
                res=path[i];
            }
        }
        return res;
    }

    private void dfs(int i){
        //遍历后置节点
        for(int j=1;j<=n;j++){
            //跟新以j结尾的路径
            if(graph[i][j]==1&&w[j]<w[i]+potatoNum[j-1]){
                w[j]=w[i]+potatoNum[j-1];
                path[j]=path[i]+"-"+String.valueOf(j);
                dfs(j);
            }
        }
    }
}

3.复杂度分析

时间复杂度：递归的最大深度是n，递归外面还有一层遍历，其他循环都是线性的，所以时间复杂度为 $O(n^2)$ 。
空间复杂度：需要额外大小为 $n+1$ 的权值数组和路径数组，以及大小为 $(n+1)^2$ 的邻接矩阵，所以空间复杂度为 $O(n^2)$ 。

方法二（动态规划）

1.解题思路

首先初始化权值数组和路径数组。
然后初始化图的邻接矩阵，记录每个节点可达的后置节点。
从后往前依次确认起点为该节点的对应路径中权值最大的，这一步，遍历所有后置节点，找权值最大的进行拼接，再跟新权值数组和路径数组。
最后取权值最大的路径。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param potatoNum int一维数组 依次表示序号为1,2,3..的节点的权值
     * @param connectRoad int二维数组 每个一维数组[x,y]表示从第x号到第y号有路
     * @return string
     */
    public String digSum (int[] potatoNum, int[][] connectRoad) {
        //初始化权值数组和路径数组
        int n=potatoNum.length;
        int[] w=new int[n+1];
        String[] path=new String[n+1];

        //初始化图的邻接矩阵
        int[][] graph=new int[n+1][n+1];
        for(int[] road:connectRoad){
            graph[road[0]][road[1]]=1;
        }
        //从后往前依次确认起点为该节点的对应路径中权值最大的
        for(int i=n;i>=1;i--){
            w[i]=potatoNum[i-1];
            path[i]=String.valueOf(i);
            int max=0;
            int id=0;
            //遍历所有后置节点，找权值最大的进行拼接
            for(int j=1;j<=n;j++){
                if(graph[i][j]==1&&max<w[j]){
                    max=w[j];
                    id=j;
                }
            }
            //跟新权值数组和路径数组
            if(max==0) continue;
            w[i]+=w[id];
            path[i]=path[i]+"-"+path[id];
        }
        int max=0;
        String res="";
        //取权值最大的路径
        for(int i=1;i<=n;i++){
            if(max<w[i]){
                max=w[i];
                res=path[i];
            }
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：寻找后置节点时，需要一层遍历，外面还有一层遍历，其他循环都是线性的，所以时间复杂度为 $O(n^2)$ 。
空间复杂度：需要额外大小为 $n+1$ 的权值数组和路径数组，以及大小为 $(n+1)^2$ 的邻接矩阵，所以空间复杂度为 $O(n^2)$ 。