Add dynamic programming on DAG using topological sort (longest path).

[sujalxverma]

Hi, I would like to contribute an implementation of dynamic programming on DAGs using topological sorting.

Proposed:

• Reusable DP on DAG template.
• Example: longest path in a DAG.
• Time complexity: O(V + E).

I noticed that topological sort is already implemented, but there is no example showing how to combine it with dynamic programming on DAGs.

Would this be a suitable addition? I will follow the existing coding style and include tests.

[williamfiset]

There's an example of the shortest path on a DAG in the topo sort file, I think this is what you mean?:

https://github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/graphtheory/TopologicalSortAdjacencyList.java#L81

[sujalxverma]

Thanks for pointing that out — I see the shortest path example in the topo sort implementation.

My intention is slightly different: rather than adding another problem-specific example, I’m proposing a reusable DP-on-DAG template that explicitly separates:
• topological ordering
• DP state definition
• transition logic

The current shortest path implementation demonstrates one application, but it doesn’t make the underlying pattern obvious or reusable for other problems like:
• longest path in DAG
• path counting
• generic DP transitions on DAGs

I believe adding a small, well-documented template + a clean example would improve the educational value of the repository by making this pattern explicit.

[williamfiset]

Feel free to send a PR

[williamfiset]

Fixed in #1313