LeetCode：1857. 有向圖中最大顏色值

本題乍一看和求所有路徑中的最長路徑?jīng)]啥區(qū)別，直接暴力枚舉所有路徑，但是時間復雜度不允許我們這樣做。

1.問題分析

數(shù)據(jù)結構：圖的拓撲排序與關鍵路徑

其實關鍵路徑就是使用了動態(tài)規(guī)劃解法，它先將有向無環(huán)圖進行拓撲排序，然后按照拓撲序進行動態(tài)規(guī)劃。

• 有向無環(huán)圖一定存在拓撲排序
• 按照拓撲序順序遍歷，每次更新該結點的后繼，按照這個方法，遍歷到某結點時一定能夠保證其前驅都已經(jīng)遍歷過并且進行過更新。我們并不需要關心具體的順序是什么，但一定有邊$<u,v>$，$u$的狀態(tài)能夠更新$v$。

因此本題也可以使用拓撲排序+動態(tài)規(guī)劃。

2.代碼解析

我們定義一個$dp[i][c]$表示第$i$個節(jié)點的顏色$c$。

則必有：$dp[i][c]=max(dp[i_{pre}][c])+I(i_{pre},i)$

• 求到達第$i$個節(jié)點時 能夠包含的最多顏色$c$的個數(shù)，等價于到達其前驅$i_{pre}$能夠包含的最多顏色$c$的個數(shù)再一步到達$i$包含的個數(shù)。

class Solution {
public:int largestPathValue(string colors, vector<vector<int>>& edges) {vector<vector<int>> dp(colors.size(), vector<int>(26, 0));vector<int> inDegrees(colors.size(), 0);vector<vector<int>> graph(colors.size());for(int i = 0; i < edges.size(); ++i){inDegrees[edges[i][1]] ++;graph[edges[i][0]].emplace_back(edges[i][1]);}vector<int> topo;//拓撲序queue<int> q;for(int i = 0; i < colors.size(); ++ i){if(inDegrees[i] == 0){q.push(i);}}while(!q.empty()){int u = q.front(); q.pop();topo.emplace_back(u);for(auto & v : graph[u]){-- inDegrees[v];if(inDegrees[v] == 0) {q.push(v);}}}int ans = 0;for(auto & u : topo){for(int i = 0; i < 26; ++ i){if(colors[u] == 'a' + i) dp[u][i] ++;ans = max(ans, dp[u][i]);for(auto & v : graph[u]){dp[v][i] = max(dp[u][i], dp[v][i]);}}}if(topo.size() != colors.size()) return -1;return ans;}
};

可以進行進一步優(yōu)化：
（1）拓撲排序的過程中更新，這樣就不用求出拓撲序了，因為排序的過程中就是拓撲序了，所以邊排序邊更新狀態(tài)。
（2）ans的求解使用$ans=max(ans,dp[u][colors[u]{?}^{\prime }{a}^{\prime }])$，原因在于，任何一個顏色最大路徑，該顏色的最后一個結點都會被遍歷到，用該結點就能求出最大值。
（3）由于是固定大小的數(shù)組，直接使用array即可。（這是加速的關鍵）
使用vector<int>(26, 0)：

使用array<int, 26>：

這說明在不使用動態(tài)數(shù)組的情況下，固定大小的靜態(tài)數(shù)組使用array比vector快很多。

class Solution {
public:int largestPathValue(string colors, vector<vector<int>>& edges) {vector<array<int, 26>> dp(colors.size());vector<int> inDegrees(colors.size(), 0);vector<vector<int>> graph(colors.size());for(int i = 0; i < edges.size(); ++i){inDegrees[edges[i][1]] ++;graph[edges[i][0]].emplace_back(edges[i][1]);}queue<int> q;for(int i = 0; i < colors.size(); ++ i){if(inDegrees[i] == 0){q.push(i);}}int ans = 0;int topo = 0;while(!q.empty()){int u = q.front(); q.pop();topo ++;dp[u][colors[u] - 'a'] ++;ans = max(ans, dp[u][colors[u] - 'a']);for(auto & v : graph[u]){-- inDegrees[v];if(inDegrees[v] == 0) {q.push(v);}for(int i = 0; i < 26; ++ i){dp[v][i] = max(dp[u][i], dp[v][i]);}}}if(topo != colors.size()) return -1;return ans;}
};

好的，讓我們詳細解釋這段代碼。該代碼的目的是解決一個有向圖中的最大路徑值問題，其中每個節(jié)點都有一個顏色。目標是找到從圖的起點到終點路徑中某種顏色出現(xiàn)最多的次數(shù)。

2.1 代碼步驟

1. 初始化數(shù)據(jù)結構

vector<array<int, 26>> dp(colors.size());
vector<int> inDegrees(colors.size(), 0);
vector<vector<int>> graph(colors.size());

• dp：一個二維數(shù)組，dp[i][j] 表示從起點到節(jié)點 i 的路徑中顏色 j（用0到25表示）的最大出現(xiàn)次數(shù)。
• inDegrees：記錄每個節(jié)點的入度。
• graph：表示圖的鄰接表。

2. 構建圖和入度數(shù)組

for(int i = 0; i < edges.size(); ++i){inDegrees[edges[i][1]]++;graph[edges[i][0]].emplace_back(edges[i][1]);
}

• 遍歷 edges，填充 inDegrees 和 graph。
• 對于每一條邊 (u, v)，增加 v 的入度，并在 graph[u] 中添加 v。

3. 初始化隊列

queue<int> q;
for(int i = 0; i < colors.size(); ++i){if(inDegrees[i] == 0){q.push(i);}
}

• 初始化一個隊列 q，將所有入度為 0 的節(jié)點入隊。這些節(jié)點作為拓撲排序的起點。

4. 拓撲排序和動態(tài)規(guī)劃

int ans = 0;
int topo = 0;
while(!q.empty()){int u = q.front(); q.pop();topo++;dp[u][colors[u] - 'a']++;ans = max(ans, dp[u][colors[u] - 'a']);for(auto & v : graph[u]){--inDegrees[v];if(inDegrees[v] == 0) { q.push(v); }for(int i = 0; i < 26; ++i){dp[v][i] = max(dp[u][i], dp[v][i]);}}
}

• ans：記錄路徑上顏色出現(xiàn)的最大次數(shù)。
• topo：記錄拓撲排序的節(jié)點數(shù)量，用于檢測是否存在環(huán)。

主要邏輯：

• 取隊首節(jié)點 u，更新 topo。
• 更新 dp[u][colors[u] - 'a']，表示節(jié)點 u 的顏色出現(xiàn)次數(shù)增加。
• 更新 ans 為當前顏色出現(xiàn)的最大次數(shù)。
• 遍歷 u 的鄰接節(jié)點 v：
  • 減少 v 的入度。
  • 如果 v 的入度為 0，入隊 q。
  • 更新 dp[v]，根據(jù)從 u 到 v 的路徑更新 v 的顏色出現(xiàn)次數(shù)。

5. 檢查是否存在環(huán)并返回結果

if(topo != colors.size()) return -1;
return ans;

• 如果拓撲排序遍歷的節(jié)點數(shù)量不等于 colors 的長度，說明圖中存在環(huán)，返回 -1。
• 否則，返回 ans，即路徑上某種顏色的最大出現(xiàn)次數(shù)。

3. 問題擴展

1. 最長路徑問題（DAG）

問題描述：
在一個有向無環(huán)圖（DAG）中找到從一個起點到終點的最長路徑。

解決方案：

1. 使用拓撲排序確定處理節(jié)點的順序。
2. 按照拓撲序進行動態(tài)規(guī)劃，計算每個節(jié)點的最長路徑長度。

2. 最短路徑問題（DAG）

問題描述：
在一個有向無環(huán)圖（DAG）中找到從一個起點到終點的最短路徑。

解決方案：

1. 使用拓撲排序確定處理節(jié)點的順序。
2. 按照拓撲序進行動態(tài)規(guī)劃，計算每個節(jié)點的最短路徑長度。

3. 最大路徑和問題

問題描述：
在一個有向無環(huán)圖（DAG）中找到從起點到終點的路徑中權重總和最大的路徑。

解決方案：

1. 使用拓撲排序確定處理節(jié)點的順序。
2. 按拓撲序進行動態(tài)規(guī)劃，計算每個節(jié)點的路徑權重總和。

4. 路徑計數(shù)問題

問題描述：
計算從起始點到終點的所有可能路徑的數(shù)量。

解決方案：

1. 使用拓撲排序確定處理節(jié)點的順序。
2. 按拓撲序計算從起始點到每個節(jié)點的路徑數(shù)量。

5. 關鍵路徑法（Critical Path Method, CPM）

問題描述：
在項目管理中，給定一組任務及其依賴關系，找出項目的關鍵路徑和項目的最短完成時間。

解決方案：

1. 使用拓撲排序確定任務的處理順序。
2. 按拓撲序進行動態(tài)規(guī)劃，計算每個任務的最早開始時間和最晚開始時間，從而確定關鍵路徑。

6. DAG上的單源最短路徑（Single Source Shortest Path in DAG）

問題描述：
在一個有向無環(huán)圖（DAG）中找到從一個起點到所有其他節(jié)點的最短路徑。

解決方案：

1. 使用拓撲排序確定處理節(jié)點的順序。
2. 按拓撲序進行動態(tài)規(guī)劃，計算從起點到每個節(jié)點的最短路徑長度。

7. 有向無環(huán)圖中的最大子序列和問題

問題描述：
在一個有向無環(huán)圖（DAG）中找到從起點到終點的最大子序列和。

解決方案：

1. 使用拓撲排序確定處理節(jié)點的順序。
2. 按拓撲序進行動態(tài)規(guī)劃，計算每個節(jié)點的最大子序列和。

8. DAG中的最長遞增子序列問題

問題描述：
在一個有向無環(huán)圖（DAG）中找到從起點到終點的最長遞增子序列。

解決方案：

1. 使用拓撲排序確定處理節(jié)點的順序。
2. 按拓撲序進行動態(tài)規(guī)劃，計算每個節(jié)點的最長遞增子序列長度。

9. 資源分配問題（DAG）

問題描述：
在一個有向無環(huán)圖（DAG）中，給定每個節(jié)點的資源需求和資源量，計算從起點到終點的最大資源分配路徑。

解決方案：

1. 使用拓撲排序確定處理節(jié)點的順序。
2. 按拓撲序進行動態(tài)規(guī)劃，計算每個節(jié)點的最大資源分配路徑。