Intro
Learning an algorithm requires us to know a lot about the physical properties of this algorithm. You have to know why you use it. Say daynamic programming, when you meet a problem, someone says "DP Obviously." Then you can solve it in a few dozens of minutes.
But have you ever thought about the motivation of using this famous algorithm, or, this famous way thinking about a problem.
This blog writes Your coach may have thousands of different ways to explain, or just start with "knapsack problem" without telling the reason.
Then what is dynamic programming in fact? Let us see.
Preface: GPT's answer
As ChatGPT being widely used, if interested, see its answer below:
Click
Dynamic programming is a technique used in computer science and mathematics to solve optimization problems by breaking them down into smaller overlapping subproblems and solving each subproblem only once, storing the results for future reference. It is applicable to problems that can be divided into smaller, overlapping subproblems and exhibit the principle of optimality.
The main idea behind dynamic programming is to solve a problem by solving its subproblems and combining their solutions to obtain the optimal solution for the original problem. This approach avoids redundant computations by storing the solutions of subproblems in a table or cache.
Dynamic programming involves the following steps:
-
Characterize the structure of the optimal solution: Determine the characteristics of the problem that allow it to be divided into smaller subproblems.
-
Define the value of the optimal solution recursively: Express the value of the optimal solution in terms of the values of the optimal solutions to its subproblems.
-
Compute the value of the optimal solution in a bottom-up manner: Solve the subproblems in a specific order, usually starting from the smallest subproblem and working towards the larger problem. Store the solutions to subproblems in a table or cache.
-
Construct an optimal solution: Once the optimal values are computed, determine how to construct the optimal solution based on the stored information.
Dynamic programming is particularly useful when a problem exhibits overlapping subproblems, meaning that the same subproblems are solved multiple times. By storing the solutions to subproblems, dynamic programming eliminates redundant computations and improves efficiency.
Common examples of problems that can be solved using dynamic programming include the knapsack problem, shortest path problem, sequence alignment problem, and many others. Dynamic programming is widely used in various fields, such as computer science, operations research, economics, and bioinformatics, to solve complex optimization problems efficiently.
Well, he says particularly correct, but since it collects a huge amount of information from the internet and uncountable people've mentioned "knapsack problem" for the beginner's dynamic programming, but today we are not.