当前位置:网站首页>动态规划思想《从入门到放弃》
动态规划思想《从入门到放弃》
2022-07-06 17:16:00 【rabbit_zli】
动态规划的定义
将原问题拆解成若干子问题 ,同时保存子问题的答案,使得每个子问题只求解一次,最终获得原问题的答案。
动态规划的一般流程
例子1:一维空间的动态规划
题目:求斐波那契数列
- 暴力递归解决
// 使用递归解决
int fibonacci(int i) {
return i <= 1 : i : fibonacci(i - 1) + fibonacci(i - 2);
}
暴力递归的时间复杂度是指数级,我们需要使用记忆化搜索去解决这个问题
- 记忆化搜索(动态规划思想)
// 使用动态规划思想 记忆化搜索
int fibonacci(int fib) {
// 定义一个数组 存储第N项的斐波那契数
int[] cache = new int[fib + 1];
// 遍历
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];
}
复杂的动态规划
复杂的动态规划:
- 维度变化了 有可能是二维或三维空间;
- 中间可能会有取舍最优子结构
题目2:不同路径
题目描述:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
对于上述问题,由于每次只能 向右或向下 走,于是我们可以转变为子问题:
子问题1:对于A如何走到右下角
子问题2:对于B如何走到右下角
所以总共的走法就等于 【A】的子问题的解+【B】的子问题的解
- 解法一:使用常规的递归解法
// 使用递归的解法
int paths(int m, int n) {
// 定义一个二维网格
int[][] table = new int[m][n];
// 调用递归函数
return dfs(table, 0, 0);
}
int dfs(int[][] table, int row, int col) {
// 递归终止条件
// 1.1 处理边界值
if (row < 0 || row >= table.length || col < 0 || col >= table[0].length) {
return 0;
}
// 1.2 若走到目的地 则返回1
if (row == table.length - 1 && col == table[0].length - 1) {
return 1;
}
// 转换成子问题的解
return dfs(table, row + 1, col) + dfs(table, row, col + 1);
}
- 解法二:记忆化搜索
/** 使用动态规划思想解决 可以发现 每一格的路径数量是由其上一格和左边一格的路径总数决定的 */
int paths(int m, int n) {
// 定义一个二维矩阵
int[][] table = new table[m][n];
// 先初始化第一行和第一列
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];
}
边栏推荐
- Telerik UI 2022 R2 SP1 Retail-Not Crack
- 第四篇,STM32中断控制编程
- Matlab learning notes
- 批量获取中国所有行政区域经边界纬度坐标(到县区级别)
- 【JokerのZYNQ7020】AXI_EMC。
- build. How to configure the dependent version number in the gradle file
- Link sharing of STM32 development materials
- Web project com mysql. cj. jdbc. Driver and com mysql. jdbc. Driver differences
- How to get started and improve test development?
- Advanced learning of MySQL -- basics -- basic operation of transactions
猜你喜欢
AI super clear repair resurfaces the light in Huang Jiaju's eyes, Lecun boss's "deep learning" course survival report, beautiful paintings only need one line of code, AI's latest paper | showmeai info
Part VI, STM32 pulse width modulation (PWM) programming
Configuring the stub area of OSPF for Huawei devices
pyflink的安装和测试
第五篇,STM32系统定时器和通用定时器编程
C9 colleges and universities, doctoral students make a statement of nature!
Dell笔记本周期性闪屏故障
深入探索编译插桩技术(四、ASM 探秘)
equals()与hashCode()
【批處理DOS-CMD命令-匯總和小結】-字符串搜索、查找、篩選命令(find、findstr),Find和findstr的區別和辨析
随机推荐
迈动互联中标北京人寿保险,助推客户提升品牌价值
Threejs image deformation enlarge full screen animation JS special effect
【软件逆向-求解flag】内存获取、逆变换操作、线性变换、约束求解
C Primer Plus Chapter 14 (structure and other data forms)
5种不同的代码相似性检测,以及代码相似性检测的发展趋势
[Batch dos - cmd Command - Summary and Summary] - String search, find, Filter Commands (FIND, findstr), differentiation and Analysis of Find and findstr
Deep learning environment configuration jupyter notebook
Advantages and disadvantages of code cloning
Article management system based on SSM framework
Slow database query optimization
tensorflow 1.14指定gpu运行设置
Deep understanding of distributed cache design
build. How to configure the dependent version number in the gradle file
Mujoco finite state machine and trajectory tracking
Part IV: STM32 interrupt control programming
【批处理DOS-CMD命令-汇总和小结】-字符串搜索、查找、筛选命令(find、findstr),Find和findstr的区别和辨析
pyflink的安装和测试
【JokerのZYNQ7020】AXI_EMC。
Activereportsjs 3.1 Chinese version | | | activereportsjs 3.1 English version
Lombok makes ⽤ @data and @builder's pit at the same time. Are you hit?