Dynamic Programming

DYNAMIC PROGRAMMING

? ? ? A technique where we solve #subproblems and use their #solutions to compute the bigger problem. The problem has an #optimal #substructure - used to find the optimal solution to subproblems

Approaches to implement DP

? ? ? ? Tabulation -> bottom up ?-- starting from the base case

? ? ? ? Memoization -> top down ?-- start from top and iterate until the base case is achieved ?-- helps avoid unnecessary #redundant #computation of the same #subproblem

Which one is Better?

? ? ? ? -> bottom up - usually #computes #faster - logical order is preserved

? ? ? ? -> top down - #easier to write - overhead due to use of #recursion - no logical order

When to use DP?

? ? ? ? -> problem can be broken down into #smaller #overlapping solutions

? ? ? ? -> problem has an #optimal #substructure

Characteristics to Identify whether to Implement DP or not:

? ? ? ? -> problem asks for something optimal - min or max

? ? ? ? -> longest possible - shortest possible

? ? ? ? -> finding #subsequences - substrings

? ? ? ? -> Later #decisions depend on earlier decisions

These are just some characteristics. The real-world problem may differ depending upon the scenario.

? ? ? ?