DP on a DAG
Many dynamic programming problems can be represented as a directed acyclic graph (DAG).
In dynamic programming, a problem is broken down into subproblems.
Each subproblem corresponds to a state.
In a DAG:
If from state you can move to state , then in the DAG there is an edge:
In DP, transitions must not form cycles:
Therefore, the state graph is acyclic.
A directed acyclic graph is given.
Find the length of the longest path.
Let:
Then for each edge:
we have the transition:
Base:
Answer:
A directed graph with vertices and edges is given.
Each vertex is assigned a lowercase Latin letter.
Path value — the maximum number of occurrences of the same letter on this path.
Example:
abaca → value (letter a)
It is required to find a path with the maximum value.
If there is a cycle in the graph, the answer is considered infinite → output .
If the graph is acyclic, you can do DP over the DAG.
Let:
where:
For the edge:
update:
Use topological sorting (Kahn):
If fewer than vertices are processed → there is a cycle.
const int MAXN = 100005;
int dp[MAXN];
int longestPathFromNode(int v, const vector<vector<int>>& g) {
if (dp[v] != -1) return dp[v];
dp[v] = 1;
for (int u : g[v]) {
dp[v] = max(dp[v], 1 + longestPathFromNode(u, g));
}
return dp[v];
}
int longestPath(int N, const vector<vector<int>>& g) {
memset(dp, -1, sizeof(dp));
int ans = 0;
for (int v = 1; v <= N; v++) {
ans = max(ans, longestPathFromNode(v, g));
}
return ans;
}
int solve(int n, vector<vector<int>>& edges, string s) {
vector<int> deg(n + 1);
vector<vector<int>> g(n + 1);
// build the graph
for (int v = 1; v <= n; v++) {
for (int u : edges[v]) {
g[v].push_back(u);
deg[u]++;
}
}
vector<vector<int>> f(n + 1, vector<int>(26, 0));
queue<int> q;
// starting vertices
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) {
q.push(i);
f[i][s[i-1] - 'a'] = 1;
}
}
int cnt = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
cnt++;
for (int u : g[v]) {
for (int c = 0; c < 26; c++) {
f[u][c] = max(
f[u][c],
f[v][c] + (c == s[u-1] - 'a')
);
}
deg[u]--;
if (deg[u] == 0)
q.push(u);
}
}
if (cnt != n)
return -1;
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int c = 0; c < 26; c++) {
ans = max(ans, f[i][c]);
}
}
return ans;
}