Eligibility for solving using Dynamic Programming

1
votes

For a problem to be solved using dp, do we need both optimal substructure and overlapping subproblems to be satisfied by the problem or any one condition makes it eligible to solve using dp techniques?

If a problem P1 has optimal substructure but subproblems arent overlapping and if P2 has overlapping substructure but optimal substructure isnt satisfied, can i still solve P1 and P2 using dp?

1
algorithmdynamic-programming

1 Answers

3
votes

It depends on a problem, but it seems that both P1 and P2 are a poor match for dynamic programming:

  • P1 - you can use DP, but you won't get any performance improvements, because the problems are not overlapping and you can't reuse solutions.
  • P2 - if there is no optimal substructure then having a solution to the subproblem does not you help find solution for the larger problem.