Dynamic programming

Understanding Dynamic Programming

• Dynamic programming is an approach used to solve complex problems by breaking them down into simpler subproblems and tackling each one individually.
• This method treats each subproblem as if it was a standalone problem and solves it. The results of these subproblems are stored so they don’t need to be solved again.
• Overlapping subproblems is a key characteristic of problems that can be solved using dynamic programming.

Stages in Dynamic Programming

• A stage in dynamic programming is a subproblem within the larger problem. Stages are defined in terms of choices or decisions that must be made.
• The stages along with the decision variables make up the state description of a problem.
• Decisions made at one stage can impact options available at future stages, this is known as the principle of optimality.

Dynamic Programming Algorithms

• An algorithm is a step-by-step process used to solve a problem or accomplish some end. In dynamic programming, the algorithm needs to be developed carefully to ensure that all subproblems are solved and the information is used correctly.
• Dynamic programming can use a bottom-up approach where the smallest subproblems are solved first, or a top-down approach where the problem is broken into subproblems but the largest subproblem is computed first.

Dynamic Programming in Decision-making

• Dynamic programming offers effective solutions for decision-making problems that involve a sequence of actions.
• This approach can help optimise resources, minimise costs or maximise profits in various scenarios such as resource allocation, production scheduling, or less tangible fields like strategic planning and policy making.