dp is applicable when you can construct solution to the given instance from solutions to subinstances of smaller problems of the same kind in addition to optimization problemsdp is also applicable to counting and decision problems--any problem where you can express solution recursively in terms of the same computation on smaller instances although conceptually dp involves recursionoften for efficiency the cache is built "bottomup" iteratively when dp is implemented recursively the cache is typically dynamic data structure such as hash table or bstwhen it is implemented iteratively the cache is usually oneor multi-dimensional array to save spacecache space may be recycled once it is known that set of entries will not be looked up again common mistake in solving dp problems is trying to think of the recursive case by splitting the problem into two equal halvesa la quicksorti solve the subproblems for subarrays [ cand [ nand combine the results howeverin most casesthese two subproblems are not sufficient to solve the original problem dp is based on combining solutions to subproblems to yield solution to the original problem howeverfor some problems dp will not work for exampleif you need to compute the longest path from city to city without repeating an intermediate cityand this longest path passes through city then the subpaths from city to city and city to city may not be individually longest paths without repeated cities table top tips for dynamic programming solutiona brute-force approach is to enumerate all possible paths this can be done using recursion howeverthere is combinatorial explosion in the number of pathswhich leads to huge time complexity the problem statement asks for the number of pathsso we focus our attention on that key observation is that because paths must advance down or rightthe number of ways to get to the bottom-right entry is the number of ways to get to the entry immediately above itplus the number of ways to get to the entry immediately to its left let' treat the origin ( as the top-left entry generalizingthe number of ways to get to (ijis the number of ways to get to ( jplus the number of ways to get to (ij (if or there is only one way to get to (ijfrom the origin this is the basis for recursive algorithm to count the number of paths implemented naivelythe algorithm has exponential time complexity--it repeatedly recurses on the same locations the solution is to cache results for examplethe number of ways to get to (ijfor the configuration in figure on the previous page is cached in matrix as shown in figure on the facing page def number_of_ways (nm)def compute_number_of_ways_to_xy (xy)if = = return if number_of_ways [ ][ =