题解 | #权值最大的路径#_牛客博客 (nowcoder.net)【转载】
题意整理
- 给定一个有向无环图，每个节点都有一个权值。
- 求所有路径中，节点权值和最大的路径。
方法一（记忆化递归）
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，递归外面还有一层遍历，其他循环都是线性的，所以时间复杂度为�(�2)O(n2)。
- 空间复杂度：需要额外大小为�+1n+1的权值数组和路径数组，以及大小为(�+1)2(n+1)2的邻接矩阵，所以空间复杂度为�(�2)O(n2)。
方法二（动态规划）
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.复杂度分析
- 时间复杂度：寻找后置节点时，需要一层遍历，外面还有一层遍历，其他循环都是线性的，所以时间复杂度为�(�2)O(n2)。
- 空间复杂度：需要额外大小为�+1n+1的权值数组和路径数组，以及大小为(�+1)2(n+1)2的邻接矩阵，所以空间复杂度为�(�2)O(n2)。