Basic Principles and Applications of Dynamic Programming

Description
Dynamic Programming (DP) is an algorithmic approach for solving complex problems, often used for optimization (such as finding the maximum, minimum, or counting). Its core idea is to break down the original problem into overlapping subproblems, solve the subproblems and store their results (to avoid redundant computation), and finally combine them to obtain the solution to the original problem. Unlike the divide-and-conquer method, the subproblems in dynamic programming are typically not independent.

Step-by-Step Explanation of the Solution Process

1. Identify the Characteristics of a Dynamic Programming Problem

   • Overlapping Subproblems: The problem can be decomposed into multiple recurring subproblems (e.g., in the Fibonacci sequence, computing F(n) requires repeatedly computing F(n-1) and F(n-2)).
   • Optimal Substructure: The optimal solution of the problem contains the optimal solutions of its subproblems (e.g., in the shortest path problem, the shortest path from A to C includes the shortest path from A to B).
   • No Aftereffect (Markov Property): Once the current state is determined, subsequent decisions are not influenced by previous states (e.g., in a board path problem, the direction of movement depends only on the current position).

2. Define State and State Transition Equation

   • State Representation: Use variables (e.g., dp[i] or dp[i][j]) to represent the solution of a subproblem. For example, in the Fibonacci sequence, dp[i] represents the i-th Fibonacci number.
   • State Transition Equation: Describes the relationship between states. For example, the equation for the Fibonacci sequence is:

\[ dp[i] = dp[i-1] + dp[i-2] \quad (i \geq 2) \]

• Initialize Boundary Conditions: Determine the solution for the smallest subproblems. For example, dp[0] = 0, dp[1] = 1.

3. Choose the Computation Order: Bottom-Up or Top-Down

   • Bottom-Up (Iterative): Start from the smallest subproblem and gradually compute up to the original problem. For example, when computing the Fibonacci sequence, iterate from i=2 to i=n.
   • Top-Down (Memoization): Start recursively from the original problem, but use an array to store the results of already computed subproblems to avoid redundant calculations.

4. Optimize Space Complexity (Optional)

   • If the state transition depends only on a limited number of previous states (e.g., dp[i] only depends on dp[i-1] and dp[i-2]), a few variables can replace the entire array, reducing the space complexity from O(n) to O(1).

Example: Climbing Stairs Problem
Problem: You can climb 1 or 2 steps at a time. How many distinct ways are there to climb to the n-th step?

1. Define State: dp[i] represents the number of distinct ways to reach the i-th step.
2. State Transition Equation: To reach the i-th step, you can either take 1 step from the (i-1)-th step or 2 steps from the (i-2)-th step. Thus:

\[ dp[i] = dp[i-1] + dp[i-2] \]

3. Initialization: dp[0] = 1 (starting point), dp[1] = 1.
4. Computation Order: Bottom-up, iteratively compute from i=2 to i=n.
5. Optimization: Only two variables are needed to store the previous two states, resulting in O(1) space complexity.

Key Points

• Dynamic programming is suitable for optimization problems with overlapping subproblems.
• The core steps are defining the state, establishing the transition equation, and determining the computation order.
• In practice, it is essential to practice recognizing problem patterns (e.g., knapsack problem, longest common subsequence, etc.).