Design 2D DP on a DAG
Overview
This question evaluates mastery of dynamic programming on graphs, reasoning about directed acyclic graph ordering, bounded-length path counting, and analysis of time/space trade-offs including space-reduction techniques.
Given a directed acyclic graph G(V, E) with N nodes, M edges, a designated source s, and an integer L, design a 2D dynamic program dp[u][k] that computes, for all nodes u and 0 ≤ k ≤ L, the number of distinct paths from s to u using exactly k edges. Specify the state definition, base cases, transition function, and iteration order using a topological sort. Analyze time and space complexity, describe how to reduce space via rolling arrays, and discuss adaptations for weighted edges (e.g., shortest/longest path with at most/exactly k edges) and for counting paths to a target t.