I was reading about dynamic programming and I understood that we should not be using dynamic programming approach if the optimal solution of a problem does not contain the optimal solution of the subproblem.

The Longest path problem is very clear example on this and I understood why.

But I am not able to find out any other problem which is similar to longest path problem, where the subproblems's solution cannot be used for solving the optimal solution of parent. Can some one guide me?

  • 3
    $\begingroup$ You shouldn't use dynamic programming if it doesn't work. Here are a few examples: linear programming, linear equations, maximum matching, maximum flow. $\endgroup$ – Yuval Filmus Oct 12 '15 at 18:32
  • $\begingroup$ @YuvalFilmus thanks. what i really wanted was an example in which the subproblem fails, i will try too solve the examples you gave through dynamic programming and see if it fails (if i am able to split the above problems into subproblems) $\endgroup$ – vishnu viswanath Oct 13 '15 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.