$\begingroup$
$\endgroup$
3
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– Yuval Filmus2015年10月12日 18:32:16 +00:00Commented Oct 12, 2015 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– vishnu viswanath2015年10月13日 00:00:48 +00:00Commented Oct 13, 2015 at 0:00
-
$\begingroup$ Is longest path an instance where you can or cannot use DP? $\endgroup$Ainsley H.– Ainsley H.2021年09月01日 20:44:01 +00:00Commented Sep 1, 2021 at 20:44