Analysis of Dynamic Programming Approach for Optimal Substructure

Abstract: Algorithm in general terms is set of rules to be followed for doing a calculation. In computer science, an algorithm is a finite set of steps of well-defined instructions to perform a particular task or to solve a well-defined problem. Various type of algorithm is developed and used in the field of networking. Some may be divide and conquer algorithm other may follows the standards of dynamic programming and some may follow the greedy approach. Dynamic programming is an algorithmic approach that solves a given problem by dividing or breaking it into subproblems and further dividing that subproblems into smaller subproblems until one reach to the smallest subproblem. It stores that result of the subproblem such that if in near future that same problems encounters then that previously saved output can be reused instead of solving that problem again and again. Hence it saves sand increase the time efficiency and uses the optimal solution approach.

Keywords: Bottom-up Approach, Optimal Dynamic Programming approach, Standard dynamic programming, Fibonacci Sequence, Optimal substructure programming, Tower of Hanoi Problem, Word Break Problem, All Pair shortest Path Algorithm.