当前位置:网站首页>Dynamic planning idea "from getting started to giving up"
Dynamic planning idea "from getting started to giving up"
2022-07-07 01:04:00 【rabbit_ zli】
Definition of dynamic programming
Break up the original problem into several sub problems , At the same time, save the answers to the sub questions , So that each subproblem can be solved only once , Finally get the answer to the original question .
The general process of Dynamic Planning
Example 1: Dynamic programming of one-dimensional space
subject : Find the Fibonacci sequence
- Violent recursive solution
// Use recursion to solve
int fibonacci(int i) {
return i <= 1 : i : fibonacci(i - 1) + fibonacci(i - 2);
}
The time complexity of violent recursion is exponential , We need to use memory search to solve this problem
- Memory search ( Dynamic planning ideas )
// Using the idea of dynamic planning Memory search
int fibonacci(int fib) {
// Define an array Store the N Fibonacci number of items
int[] cache = new int[fib + 1];
// Traverse
for (int i = 0; i < cache.length; i++) {
if (fib <= 1) {
cache[i] = i;
continue;
}
cache[i] = cache[i - 2] + cache[i - 1];
}
return cache[fib];
}
Complex dynamic programming
Complex dynamic programming :
- Dimensions have changed It may be two-dimensional or three-dimensional space ;
- There may be a trade-off optimal substructure in the middle
subject 2: Different paths
Title Description : A robot is in a m x n The top left corner of the grid ( The starting point is marked as “Start” ).
The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid ( In the figure below, it is marked as “Finish” ).
Ask how many different paths there are in total ?
For the above questions , Because you can only Right or down go , So we can turn it into a sub problem :
Sub problem 1: about A How to get to the lower right corner
Sub problem 2: about B How to get to the lower right corner
So the total walking method is equal to 【A】 The solution of the subproblem +【B】 The solution of the subproblem
- Solution 1 : Use the conventional recursive solution
// Using recursive solutions
int paths(int m, int n) {
// Define a two-dimensional mesh
int[][] table = new int[m][n];
// Call recursive functions
return dfs(table, 0, 0);
}
int dfs(int[][] table, int row, int col) {
// Recursive termination condition
// 1.1 Dealing with boundary values
if (row < 0 || row >= table.length || col < 0 || col >= table[0].length) {
return 0;
}
// 1.2 If you go to your destination Then return to 1
if (row == table.length - 1 && col == table[0].length - 1) {
return 1;
}
// Transform into the solution of the subproblem
return dfs(table, row + 1, col) + dfs(table, row, col + 1);
}
- Solution 2 : Memory search
/** Use the idea of dynamic programming to solve You can find The number of paths in each grid is determined by the total number of paths in the upper grid and the left grid */
int paths(int m, int n) {
// Define a two-dimensional matrix
int[][] table = new table[m][n];
// First initialize the first row and first column
for (int i = 0; i < m; i++) {
table[m][0] = 1;
}
for (int i = 0; i < n; i++) {
table[0][n] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
table[i][j] = table[i - 1][j] + table[i][j - 1];
}
}
return table[m - 1][n - 1];
}
边栏推荐
- Zabbix 5.0:通过LLD方式自动化监控阿里云RDS
- .class文件的字节码结构
- Data sharing of the 835 postgraduate entrance examination of software engineering in Hainan University in 23
- Deep learning environment configuration jupyter notebook
- 随时随地查看远程试验数据与记录——IPEhub2与IPEmotion APP
- Leetcode (547) - number of provinces
- Batch obtain the latitude coordinates of all administrative regions in China (to the county level)
- 第七篇,STM32串口通信编程
- [batch dos-cmd command - summary and summary] - view or modify file attributes (attrib), view and modify file association types (Assoc, ftype)
- pytorch之数据类型tensor
猜你喜欢
深入探索编译插桩技术(四、ASM 探秘)
Data sharing of the 835 postgraduate entrance examination of software engineering in Hainan University in 23
Chapter II proxy and cookies of urllib Library
Building a dream in the digital era, the Xi'an station of the city chain science and Technology Strategy Summit ended smoothly
学习使用代码生成美观的接口文档!!!
【批处理DOS-CMD命令-汇总和小结】-跳转、循环、条件命令(goto、errorlevel、if、for[读取、切分、提取字符串]、)cmd命令错误汇总,cmd错误
Chenglian premium products has completed the first step to enter the international capital market by taking shares in halber international
动态规划思想《从入门到放弃》
Windows installation mysql8 (5 minutes)
Zynq transplant ucosiii
随机推荐
界面控件DevExpress WinForms皮肤编辑器的这个补丁,你了解了吗?
[batch dos-cmd command - summary and summary] - view or modify file attributes (attrib), view and modify file association types (Assoc, ftype)
Deeply explore the compilation and pile insertion technology (IV. ASM exploration)
学习光线跟踪一样的自3D表征Ego3RT
Niuke cold training camp 6B (Freund has no green name level)
筑梦数字时代,城链科技战略峰会西安站顺利落幕
C9 colleges and universities, doctoral students make a statement of nature!
Eventbus source code analysis
浅谈测试开发怎么入门,如何提升?
Rainstorm effect in levels - ue5
Telerik UI 2022 R2 SP1 Retail-Not Crack
深度学习之环境配置 jupyter notebook
Part V: STM32 system timer and general timer programming
Dell笔记本周期性闪屏故障
Interface (interface related meaning, different abstract classes, interface callback)
深度学习之线性代数
mongodb客户端操作(MongoRepository)
【JVM调优实战100例】05——方法区调优实战(下)
Build your own website (17)
Attention SLAM:一种从人类注意中学习的视觉单目SLAM