Dynamic Programming

Dynamic programming is a sequential decision-making technique. It is a recursive technique, moving from the final stage to the initial stages. A decision taken at one stage influences the decisions in other stages. This technique is useful in a large number of multi-period business problems.

Dynamic programming Exhibit the following two properties:

1. Optimal Substructure: The solution to a problem can be constructed efficiently from the solutions of its subproblems.
2. Overlapping Subproblems: The problem can be broken down into smaller, overlapping subproblems, solved multiple times in naive approaches.

Instead of repeatedly solving the same subproblem, DP solves each one once and stores its solution, typically using a table, to avoid redundant calculations.

Terms used  in dynamic programming:

• Stage: Period or logical sub-problem.
• State variables: Possible initial situations or conditions.
• Decision variables: Alternatives that exist at each stage.
• Decision criteria: Statement concerning objectives of a problem.
• Optimum policy: A set of decision rules developed due to decision criteria that gives an optimal decision.

Steps to Solve a Problem Using Dynamic Programming:

1. Define the Problem: Identify what you are solving (e.g., maximum value, shortest path).
2. Identify the State: Determine how to represent subproblems.
3. Define the Recurrence Relation: Establish the relationship between states.
4. Implement the Solution: Use memoization or tabulation to compute the result.
5. Optimize if Necessary: Reduce space complexity if possible .