首页 > 代码库 > dynamic programming
dynamic programming
1. Concepts
The idea behind dynamic programming is quite simple. In general, to solve a given problem, we need to solve different parts of the problem (subproblems), then combine the solutions of the subproblems to reach an overall solution. Often when using a more naive method, many of the subproblems are generated and solved many times. The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number of computations: once the solution to a given subproblem has been computed, it is stored or "memoized": the next time the same solution is needed, it is simply looked up. This approach is especially useful when the number of repeating subproblems grows exponentially as a function of the size of the input.
1) Dynamic programming is a method for solving complex problem by breaking them down into simpler subproblems.
2) It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure.
overlapping subproblems :
if the problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems
for example:
Fibonacci series: Fi = Fi−1 + Fi−2, with base case F1 = F2 = 1. Then F43 = F42 + F41, and F42 = F41 + F40. Now F41 is being solved in the
recursive subtrees of both F43 as well as F42
This can be achieved in either of two ways:
- Top-down approach: This is the direct fall-out of the recursive formulation of any problem. If the solution to any problem can be formulated recursively using the solution to its subproblems, and if its subproblems are overlapping, then one can easily memoize or store the solutions to the subproblems in a table. Whenever we attempt to solve a new subproblem, we first check the table to see if it is already solved. If a solution has been recorded, we can use it directly, otherwise we solve the subproblem and add its solution to the table.
- Bottom-up approach: Once we formulate the solution to a problem recursively as in terms of its subproblems, we can try reformulating the problem in a bottom-up fashion: try solving the subproblems first and use their solutions to build-on and arrive at solutions to bigger subproblems. This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger subproblems by using the solutions to small subproblems. For example, if we already know the values of F41 and F40, we can directly calculate the value of F42.
optimal substructure :
a problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. Such optimal substructures are usually described by means of recursion.
for example:
given a graph G=(V,E), the shortest path p from a vertex u to a vertex v exhibits optimal substructure: take any intermediate
vertex w on this shortest path p. If p is truly the shortest path, then it can be split into subpaths p1 from u to w and p2 from w to v
3) When applicable, the method takes far less time than naive methods that don‘t take advantage of the subproblem overlap (like depth first search)
4) There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping subproblems. If a problem can be solved by combining optimal solutions to non-overlapping subproblems, the strategy is called "divide and conquer" instead. This is why mergesort andquicksort are not classified as dynamic programming problems.
2. Example
1) Fabonnaci sequence
//recursionpublic static int fib(int n){ if(n == 0){ return 0; } if(n == 1){ return 1; } return fib(n-1) + fib(n-2); }
if we use top-down approach
//dp, top-down, use array to memoize public static int fib_dp(int n){ int[] arr = new int[n+1]; if(n == 0){ return 0; } if(n == 1){ return 1; } if(arr[n] == 0){ arr[n] = fib_dp(n-1) + fib_dp(n-2); } return arr[n]; } //dp, top-down, use map to memoize public static int fib_dp1(int n){ HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); map.put(0, 0); map.put(1, 1); if(!map.containsKey(n)){ map.put(n, fib_dp(n-1) + fib_dp(n-2)); } return map.get(n); }
if we use bottom-up approach: (time: o(n), space o(1))
//bottom-up public static int fib_dp2(int n){ if(n == 0){ return 0; } if(n == 1){ return 1; } int previous = 0, current = 1, newVal = 0; for(int i = 0; i < n-1; i++){ newVal = previous + current; previous = current; current = newVal; } return current; }
dynamic programming