当前位置:网站首页>Detailed introduction to dynamic programming (with examples)
Detailed introduction to dynamic programming (with examples)
2022-07-06 14:48:00 【sakeww】
Catalog
- Dynamic Programming:
- Topic explanation :
- The first question is : Fibonacci sequence
- The second question is : String segmentation (Word Break)
- Third question : Trigonometric matrix (Triangle)
- Fourth question : The total number of paths (Unique Paths)
- Fifth question : Minimum path sum (Minimum Path Sum)
- Sixth question : knapsack problem
- Question seven Palindrome segmentation (Palindrome Partitioning)
- The eighth question Edit distance (Edit Distance)
- Question 9 Different subsequences (Distinct Subsequences)
Dynamic Programming:
Definition :
DP Definition :
Dynamic programming is an extension of the idea of partition , Generally speaking, it means making big things small , The art of trivialization .
In the process of dividing big problems into small ones , Save the results of these small problems , And these results can be used directly when dealing with larger problems later .
characteristic :
Dynamic programming has the following three characteristics
- The original problem is decomposed into several similar subproblems .
- All subproblems need to be solved only once .
- Store the solution of the subproblem
The essence :
It is the definition of the problem state and the state transfer equation ( States and the recursive relationship between States )
Consideration angle :
Dynamic programming is generally considered from the following four perspectives :
- State definition
- The transfer equation between States is defined
- Initialization of state
- Return results
Requirements for state definition :
The defined state must form a recursive relationship
One sentence summary :
Three characteristics, four elements and two essences
Applicable scenario :
Maximum / minimum value , Not feasible , Is it right? , Number of schemes
Topic explanation :
The first question is : Fibonacci sequence
https://blog.csdn.net/sakeww/article/details/122770286
The second question is : String segmentation (Word Break)
https://blog.csdn.net/sakeww/article/details/122857096
Third question : Trigonometric matrix (Triangle)
https://blog.csdn.net/sakeww/article/details/122861135
Fourth question : The total number of paths (Unique Paths)
https://blog.csdn.net/sakeww/article/details/122863621
Fifth question : Minimum path sum (Minimum Path Sum)
https://blog.csdn.net/sakeww/article/details/122864886
Sixth question : knapsack problem
https://blog.csdn.net/sakeww/article/details/122867718
Question seven Palindrome segmentation (Palindrome Partitioning)
https://blog.csdn.net/sakeww/article/details/122894050
The eighth question Edit distance (Edit Distance)
https://blog.csdn.net/sakeww/article/details/122899542
Question 9 Different subsequences (Distinct Subsequences)
https://blog.csdn.net/sakeww/article/details/122900255
边栏推荐
- 【指针】数组逆序重新存放后并输出
- The four connection methods of JDBC are directly coded
- Proceedingjoinpoint API use
- With 27K successful entry ByteDance, this "software testing interview notes" has benefited me for life
- How to transform functional testing into automated testing?
- Fundamentals of digital circuits (III) encoder and decoder
- Zhejiang University Edition "C language programming experiment and exercise guide (3rd Edition)" topic set
- What level do 18K test engineers want? Take a look at the interview experience of a 26 year old test engineer
- Constants, variables, and operators of SystemVerilog usage
- Realize applet payment function with applet cloud development (including source code)
猜你喜欢
1. Payment system
“Hello IC World”
Uibutton status exploration and customization
Statistics 8th Edition Jia Junping Chapter 14 summary of index knowledge points and answers to exercises after class
《统计学》第八版贾俊平第三章课后习题及答案总结
《统计学》第八版贾俊平第十一章一元线性回归知识点总结及课后习题答案
数字电路基础(一)数制与码制
The salary of testers is polarized. How to become an automated test with a monthly salary of 20K?
Fundamentals of digital circuit (IV) data distributor, data selector and numerical comparator
Based on authorized access, cross host, and permission allocation under sqlserver
随机推荐
Get started with Matplotlib drawing
My first blog
150 common interview questions for software testing in large factories. Serious thinking is very valuable for your interview
内网渗透之内网信息收集(三)
[pointer] find the value of the largest element in the two-dimensional array
Zhejiang University Edition "C language programming experiment and exercise guide (3rd Edition)" topic set
What is the transaction of MySQL? What is dirty reading and what is unreal reading? Not repeatable?
Quaternion -- basic concepts (Reprint)
With 27K successful entry ByteDance, this "software testing interview notes" has benefited me for life
Es full text index
Pointer -- output all characters in the string in reverse order
Transplant hummingbird e203 core to Da Vinci pro35t [Jichuang xinlai risc-v Cup] (I)
Overview of LNMP architecture and construction of related services
Fundamentals of digital circuit (IV) data distributor, data selector and numerical comparator
Flash implements forced login
Summary of thread implementation
1.支付系统
数字电路基础(五)算术运算电路
Want to learn how to get started and learn software testing? I'll give you a good chat today
How to earn the first pot of gold in CSDN (we are all creators)