/* Dynamic Programming Explained with a Simple Example. Dynamic programming is a technique for implementing certain types of recursive algorithms efficiently. Often the time complexity of a directly recursive function can be exponential, O(2**n) */ public class dynprog { /*Sample Problem: Imagine a square grid with Cartesian coordinates. Suppose you're at coordinate x,y: how many different routes can you take to get to the origin 0,0 (assuming that no intersections are blocked). Assuming that 0,0 is at the upper left-hand corner, at each step you can either go up, or go to the left (decrement y or x). For example, one route is to go all the way up to y=0, then all the way left to x=0. Another route is go all the way left, then all the way up, and another one is to zig-zag between up and left. The different routes may intersect. What we want is the *number of different routes,* not the length of a route (which is always the same). If you're mathematically savvy, you might be able to figure out that the solution required is related to binomial coefficients, and that there is a closed (non-recursive) formula to solve the problem, which is (x+y)! number of routes = ------- x!*y! Where "!" is the factorial function, which we can implement with static int factorial(int n) { int ax = 1; while (n>1) ax *= n--; return ax; } So we can solve the problem without using recursion. But it's also possible to come up with a recursive solution, which requires two steps. 1. identify the simplest cases, i.e., the "base" cases of the problem. 2. find a way to divide the problem into smaller subproblems. By "smaller" we mean closer to the base cases. These are the recursive cases. For this problem, the base cases are when x or y is 0: that is, we're on the left- or top border, and there is only one way to get home, which is a straight line. The recursive case, for when both x,y are non-zero, we can observe that the solution is the sum of the solutions for x-1,y and x,y-1. In other words the first choice we make (left or up) will divide the solutions into two sets. Clearly both x-1,y and x,y-1 are both smaller problems as they are closer to the base cases. The "totalroutes" function in the program below implements this recursive algorithm to compute the answer. The main program calls the function with command-line arguments. */ public static long totalroutes(int x, int y) { if (x==0 || y==0) return 1; else return totalroutes(x-1,y) + totalroutes(x,y-1); } /* Unfortunately, the time complexity of this algorithm is in the category of O(2**n), where n=x+y. (I'm using the python syntax 2**n for 2 to the nth power: in java it would be (int)Math.pow(2,n).) We can write down the following recurrence relation for the time it takes for n=x+y: T(n) = 2*T(n-1) + 1 The solution of this recurrence relation is T(n) = 2**n - 1, since 2**n-1 = 2* (2**(n-1) - 1) + 1 = 2* 2**(n-1) - 2 + 1. What does this mean in practical terms? Call totalroutes(50,50) and find out! The recursive function is not a practical solution. To make the problem more interesting, so that it cannot be solved with a closed formula, we will also mark some of the coordinates as **blocked-off**. A path cannot include a blocked-off coordinate. There is no way to write a closed formula statically without knowing which coordinates are blocked. We can represent which coordinates are blocked using a 2D array of booleans: coordinate x,y is blocked off if BLOCKED[x][y]==true. The answer may be zero if enough coordinates are blocked off (you still can only go left or up). We will also need to change the base cases. */ public static long routes(int x, int y, boolean[][] BLOCKED) { if (BLOCKED[x][y]) return 0; if (x==0 && y==0) return 1; else if (x==0) return routes(x,y-1,BLOCKED); else if (y==0) return routes(x-1,y,BLOCKED); else return routes(x-1,y,BLOCKED) + routes(x,y-1,BLOCKED); } /* The worst-case complexity of this function is the same as for totalroutes: it's still O(2**n). We should be able to apply dynamic programming to speed up the function. Next Step: Implement top-down or bottom-up dynamic programming. In top-down dynamic programming (or memoization), the core function is still recursive. The problem with the inefficient recursive program is often due to the fact that there are redundant recursive calls. But we can use an array (or hashmap) to record the return value of the function each time it's called. That way, no redundant calls to the function will ever be needed. Since the sample totalroutes function take two arguments, we need a 2D array in this example: */ // Top-down dynamic programming. static long M[][]; // dynamic programming matrix, must be // declared externally to the core recursive function. // core recursive function protected static long topdown(int x, int y, boolean[][] Blocked) { if (M[x][y]==-1) // -1 means no solution recorded, compute as before { if (Blocked[x][y]) M[x][y] = 0; else if (x==0 && y==0) M[x][y] = 1; else if (x==0) M[x][y] = topdown(x,y-1,Blocked); else if (y==0) M[x][y] = topdown(x-1,y,Blocked); else M[x][y] = topdown(x-1,y,Blocked) + topdown(x,y-1,Blocked); } return M[x][y]; // return value stored in matrix, redundancy avoided. } // In this particular example, we know that -1 cannot be the correct // value computed by totalroutes, so we can use -1 to indicate that // no solution has been recorded in the matrix. // Outer interface method initializes M, calls topdown: public static long tdroutes(int x, int y, boolean[][] Blocked) { M = new long[x+1][y+1]; // create matrix of adequate size for(int i=0;i<=x;i++) java.util.Arrays.fill(M[i],-1); // fill entire array with -1 return topdown(x,y,Blocked); } /* For n = x+y, we can assume that both x and y are linearly proportional to n (for example, x = y= n/2 or x= n/3, y = 2n/3, etc). In each case, the size of the M matrix is O(n*n) (n squared). Since each value M[i][k] is computed exactly once, the complexity of this algorithm is therefore O(n*n), which is much better than O(2**n). */ /* Bottom-Up Dynamic Programming So top down dynamic programming still uses recursion in the core function, but redundant recursive calls are avoided. However, notice that to calculate the value of M[i][k], I just need the value in the row above and in the column to the left: M[i-1][k] and M[i][k-1]. Therefore, I can actually just fill the array using a nested for-loop that increments i and k. This time, the "recursive" part of the program is reduced to M referring to itself, but no recursive *calls* are made. */ // with bottom-up dynamic programming: T(n) = T(n-1) + n public static long buroutes(int x, int y, boolean[][] Blocked) { M = new long[x+1][y+1]; //must be big enough for M[x][y] to exist for(int i=0;i<=x;i++) java.util.Arrays.fill(M[i],-1); // fill entire array with -1 for(int i=0;i<=x;i++) for(int k=0;k<=y;k++) { if (Blocked[i][k]) M[i][k] = 0; else if (i==0 && k==0) M[i][k] = 1; else if (i==0) M[i][k] = M[i][k-1]; else if (k==0) M[i][k] = M[i-1][k]; else M[i][k] = M[i-1][k] + M[i][k-1]; }//for i, k return M[x][y]; }//buroutes /* This time, since no recursive calls are made, the matrix can be declared and created locally, without the need of an interface function. If x,y are both O(n), then this algorithm is clearly O(n*n): T(n) =T(n-1)+n. The "recursion" now appears in the line: M[i][k] = M[i-1][k] + M[i][k-1]; So the recursive logic is still present, but not as recursive calls. In other words we replaced ()s with []s. HOW TO CHOOSE BETWEEN BOTTOM-UP AND TOP-DOWN TECHNIQUES: For this particular example, it doesn't make much difference, and the bottom-up method has slightly less overhead, and therefore should be chosen. However, there are also some problems (see knapsack problem) where we do not need to calculate *every* value in the matrix. For example, if M[i][k] = M[i-m][k] + M[i-n][k]; where m and n are not known at compile time, then some values of the matrix may never need to be computed. In such cases, it would be better to use top-down dynamic programming. ** Extracting a Solution Often for these type of problems there are many equally-optimal solutions, and enumerating all of them will again take exponential time, so we are usually just looking for ONE possible solution. We'll find a specific path from coordinate x,y back to 0,0 as we also compute the number of possible solutions. At each step, we can either go left (x-1,y) or go up (x,y-1), and we will choose the direction **that offers the most options** - i.e. choose the direction that has the most number of routes back to 0,0. It's also possible that no solutions exist. We will record this choice in an external 2D matrix of bytes called Path. The idea is that, given any coordinate x,y, if Path[x][y]==1 then we should go up; if Path[x][y]==2 we should go left. If Path[x][y]==0, then no solution exists. The Path variable below is declared external to the last version of the routes program, which is the bottom-up solution adopted to also compute the path. */ // bottom-up solution that also computes the path matrix: static byte Path[][]; // very important Path is externally declared. // Path value 2=left, 1=up, 0=no path public static long buroutes_path(int x, int y, boolean[][] Blocked) { M = new long[x+1][y+1]; for(int i=0;i<=x;i++) java.util.Arrays.fill(M[i],-1); // fill 2D array with -1's Path = new byte[x+1][y+1]; // initially value all zeros for(int i=0;i<=x;i++) for(int k=0;k<=y;k++) { if (Blocked[i][k]) { M[i][k] = 0; Path[i][k] = 0; } else if (i==0 && k==0) { M[i][k] = 1; Path[i][k] = 3; // 3 means at destination } else if (i==0) { M[i][k] = M[i][k-1]; Path[i][k]=1; // up } else if (k==0) { M[i][k] = M[i-1][k]; Path[i][k] = 2; // left } else { long up = M[i][k-1], left=M[i-1][k]; M[i][k] = up+left; if (up+left == 0) Path[i][k] = 0; // no solution else if (up>left) Path[i][k] = 1; else Path[i][k] = 2; } }//for i,k return M[x][y]; }//buroutes_path // when function returns, Path will tell us how to get back to 0,0 public static void main(String[] av) { int x = Integer.parseInt(av[0]); // take command-line args int y = Integer.parseInt(av[1]); boolean[][] Blocked = new boolean[x+100][y+100]; // initially all false Blocked[3][4] = Blocked[5][0] = true; // two coordinates blocked //long r = totalroutes(x,y); // no dynamic programming //long r = routes(x,y,Blocked); // no dynamic programming //long r = tdroutes(x,y,Blocked); // top-down dynamic programming //long r = buroutes(x,y,Blocked); // bottom-up dynamic programming long r = buroutes_path(x,y,Blocked); //bottom-up and computer Path System.out.println("number of solutions: "+r); ////// TRACE BACK (Stage 4: ) if (Path!=null && r!=0) { // print path if one was computed System.out.println("one solution: "); while (Path[x][y]!=0 && (x!=0 || y!=0)) { if (Path[x][y]==1) { System.out.print("up "); y--; } else if (Path[x][y]==2) { System.out.print("left "); x--; } }//while System.out.println(); }//Path exists } //main }//dynprog public class /* General Summary of Dynamic Programming. Dynamic programming can reduce the time complexity of some recursive programs from exponential time, such as O(2**n) or O(n!), to polynomial or "pseudo polynomial" time, something like O(n*n) or O(n). Exponential recursive functions often have time complexities expressed by the following recurrence relations. T(n) = 2T(n-1)+1, or T(n) = 3T(n-1)+1 Such functions can't be implemented directly using recursion and still be efficient, at least not if they're implemented in a naive way. Dynamic programming can implement such programs efficiently using an array (or hashmap) to record the results of recursive computations. It involves four general stages: Stage 1: Formulate a recursive solution to the problem. This stage is all about logic and being able to think recursively, without worrying about how to implement the solution efficiently. This stop can sometimes be difficult. However, all computer science students need to be able to do stages 2, 3 and 4: Stage 2: Determine if dynamic programming can be applied as an implementation technique. If the recursive algorithm you formulated can be described by something like T(n) = 2T(n/2) +n, which is O(n log n), then there is no need to apply dynamic programming: the algorithm can be implemented directly using recursion. If it's T(n)=T(n-1)+f(n), then likely a simple loop would be better than recursion. Dynamic programming should only be used for algorithms that have exponential time complexity, such as O(2**n) or O(3**n). In these cases, dynamic programming can decrease the complexity to "polynomial time," such as O(n) or O(n*n). Dynamic programming also only works in the following situations: a. The function takes non-negative integer arguments within a reasonable range, or arguments that can be mapped to non-negative integers within a reasonable range (using a hash map, for example). Here "reasonable" refers to the size of arrays that are needed. b. The function is "stateless:" that is, the function always returns the same value on the same input: f(x)==f(x) is always true (it may not be true if f changes some external variable, or does something randomly). Dynamic programming is sometimes overused. For example, to efficiently implement the "naive" Fibonacci function: int fib(int n){if (n<3) return 1; else return fib(n-1)+fib(n-2);} it only requires two variables because we only need to know the last two fib numbers to compute the next one: there's no need for a matrix. Dynamic programming generally corresponds to problems that require "strong induction": the solution of the next problem may depend on the solutions to all smaller problems. Stage 3: If stage 2 indicates that dynamic programming should be used, now we have to actually implement it. There are usually two options: top-down dynamic programming (also called memoization), or bottom-up dynamic programming. These techniques are illustrated in the sample program. Stage 4: In practice, we usually need to extract a solution to a problem that consists of more than just a simple answer. For example, the solution may consist of a path to a destination instead of just the destination itself. In the fourth stage we often need to do a "traceback," which generally means we need to record the steps and choices we made to arrive at the optimal solution. */