当前位置:网站首页>动态规划思想《从入门到放弃》
动态规划思想《从入门到放弃》
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];
}
边栏推荐
- C9 colleges and universities, doctoral students make a statement of nature!
- Attention SLAM:一种从人类注意中学习的视觉单目SLAM
- Deep understanding of distributed cache design
- C9高校,博士生一作发Nature!
- ActiveReportsJS 3.1中文版|||ActiveReportsJS 3.1英文版
- Article management system based on SSM framework
- mongodb客户端操作(MongoRepository)
- 深度学习简史(一)
- 【批处理DOS-CMD命令-汇总和小结】-字符串搜索、查找、筛选命令(find、findstr),Find和findstr的区别和辨析
- 学习光线跟踪一样的自3D表征Ego3RT
猜你喜欢
[batch dos-cmd command - summary and summary] - string search, search, and filter commands (find, findstr), and the difference and discrimination between find and findstr
C9高校,博士生一作发Nature!
Five different code similarity detection and the development trend of code similarity detection
Hero League | King | cross the line of fire BGM AI score competition sharing
Memory optimization of Amazon memorydb for redis and Amazon elasticache for redis
Attention SLAM:一种从人类注意中学习的视觉单目SLAM
深入探索编译插桩技术(四、ASM 探秘)
Data processing of deep learning
Deep learning environment configuration jupyter notebook
Lombok makes ⽤ @data and @builder's pit at the same time. Are you hit?
随机推荐
Dell Notebook Periodic Flash Screen Fault
深度学习之线性代数
ActiveReportsJS 3.1中文版|||ActiveReportsJS 3.1英文版
以机房B级建设标准满足等保2.0三级要求 | 混合云基础设施
Installation and testing of pyflink
Periodic flash screen failure of Dell notebook
Chenglian premium products has completed the first step to enter the international capital market by taking shares in halber international
Telerik UI 2022 R2 SP1 Retail-Not Crack
Advanced learning of MySQL -- basics -- multi table query -- joint query
Dell笔记本周期性闪屏故障
Notes of training courses selected by Massey school
【批處理DOS-CMD命令-匯總和小結】-字符串搜索、查找、篩選命令(find、findstr),Find和findstr的區別和辨析
接口(接口相关含义,区别抽象类,接口回调)
Equals() and hashcode()
How to judge whether an element in an array contains all attribute values of an object
. Bytecode structure of class file
Linear algebra of deep learning
Link sharing of STM32 development materials
Provincial and urban level three coordinate boundary data CSV to JSON
【批处理DOS-CMD命令-汇总和小结】-跳转、循环、条件命令(goto、errorlevel、if、for[读取、切分、提取字符串]、)cmd命令错误汇总,cmd错误