Dynamic Programming
Time complexity is a function describing the amount of time an algorithm.. space complexity is a function describing the amount of memory space an algorithm. Since there are three calls to count Ways DP the time complexity is O(3n) which is an element of O(n). The space complexity would be O(n+n) one n for the size of map and one n for the recursive call stack, which is also an element of O(n).
dynamic programming was invented by Richard E.bellman in 1950.
Timeit module, line profiler module for line by line analysis.
Multi stage decision process is the concept of dividing a problem into further sub problems and then solving them sequentially. In multistage decision problems, an N variable problem is represented by N single variable problems.
The main concept of dynamic programming is straight-forward. We divide a problem into smaller nested subproblems, and then combine the solutions to reach an overall solution.
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.
Backward induction in game theory is an iterative process of reasoning backward in time, from the end of a problem or situation, to solve finite extensive form and sequential games, and infer a sequence of optimal actions.
A problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem.
Dynamic programming uses the results of the subproblems of a problem so that every subproblem is solved only once whereas recursion and memoization use repeated computations of the same procedure of a problem.
The Pros of Memoization is: Memoization is a method of dynamic programming which avoids the overlapping substructure problem and solves the substructure at once only it has ability to stores the solutions of a substructure on the memory.
and the Cons of Memoization is: It takes some time to solves the subproblem as compared to the Tabulation method. It is using recursion which takes extra memory known as stack memory.
pros: To Simplify Complex Data, To Facilitate Comparison Analysis And Interpretation
Tabulation facilitates comparison, analysis and interpretation of data easily with the help of statistical measures such as averages, dispersion, correlation, regression, deviations etc.
Provide Reference
Tabulated data and information can be used in different researches and studies. So, it also serves as a source of reference. cons: Tables contain only numerical data. They do not contain details. qualitative expression is not possible through tables. Tables can be used by experts only to draw conclusions.
The bottom-up method to data science tends to be unstructured and exploratory. It lets the data lead to a result, while the top-down method defines a problem to be solved and constructs an experiment to solve it.
Rabbit example describes the Fibonacci series.
Greddy algorithm will choose what is best at the moment but dynamic programming will decide on what is needed for optimal solution.