It’s a general powerful algorithm design technique. It is a careful exhaustive search. Exhaustive search are usually not good because they are exponential time but if we find a dynamic programming algorithm then it solves the problem in polynomial time. It is mostly used to solve optimisation problem, i.e., problem required to maximise something or to minimise something. Richard bellman is considered as the founder of this theory and he named it as a dynamic programming. The fundamental idea of dynamic programming is to reduce the problem into a bunch of subproblems such that some subproblems occur many times, so if we solve the subproblem once and use its result at other places then the computational complexity of the problem will be significantly reduced.
Bellman explained that tell me the name dynamic programming to hide the fact that he is doing mathematical research. …
- Memorisation and subproblem
- Shortest path
- Guessing and DAG view
F1 = F2 = 1 Fn = Fn-1 + Fn-2
A naive recursive algorithm to compute the Fibonacci number will be the following
fib(n): if n <= 2: f = 1 else: f = fib(n-1)+fib(n-2) return f
Running time of above algorithm is exponential as we see below
So naive recursive algorithm is a bad algorithm.
Memorised based Dynamic programming algorithm
So the idea is to store the value of Fibonacci number in an empty dictionary once we compute it and use it later when needed.
So DP is
- Memorise and reuse solution to subproblems, that helps to solve the actual problem.
- Time = # subproblems x (time per subproblems)
Bottom up dynamic programming algorithm
We can generalise this algorithm with following properties
- It will do the same number of competition as memorised version of dynamic programming.
- Topology sort of subproblem dependency DAG
- It often saves space.
The problem is to find the ::shortest path:: from a fixed node to all other nodes. S(s,v), for all v.
We will analyse the problem the same way we have done to Fibonacci numbers. We will first write the naive recursive algorithm then a memorised DP algorithm, finally we will write a bottom up algorithm.
Alternatively we start from last, This is our naive recursive algorithm and we hope that it will not be great, and it is really not good as it is exponential. But we know how we can make it better using memorisation. We will memorise the value of S(s,u) for all u in the graph.
In this case case the algorithm will runs infinitely many times. This represent the presence of cycle in the graph.
This is typed using a Microsoft keyboard. This is great keyboard. It is small so it will take some time to get used to it.