At each vertex, we need to minimize the cost over all its 2 K − 1 predecessor nodes, and, for each such transition, we need to estimate the SOP objective function that requires O(K 2 ) operations.
the dynamic programming algorithm has time complexity of O(K 2 2 K N K ) and space complexity of O(N K ), which is infeasible for most practical problem instances.