当前位置:网站首页>动态规划思想《从入门到放弃》
动态规划思想《从入门到放弃》
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];
}
边栏推荐
- Leetcode (547) - number of provinces
- [batch dos-cmd command - summary and summary] - view or modify file attributes (attrib), view and modify file association types (Assoc, ftype)
- pyflink的安装和测试
- Building a dream in the digital era, the Xi'an station of the city chain science and Technology Strategy Summit ended smoothly
- Article management system based on SSM framework
- Advantages and disadvantages of code cloning
- Address information parsing in one line of code
- 第四篇,STM32中断控制编程
- 深度学习之数据处理
- Three methods to realize JS asynchronous loading
猜你喜欢
Deep learning environment configuration jupyter notebook
城联优品入股浩柏国际进军国际资本市场,已完成第一步
C9 colleges and universities, doctoral students make a statement of nature!
pyflink的安装和测试
建立自己的网站(17)
Deep understanding of distributed cache design
[C language] dynamic address book
Chapter II proxy and cookies of urllib Library
Configuring OSPF basic functions for Huawei devices
Telerik UI 2022 R2 SP1 Retail-Not Crack
随机推荐
深度学习之环境配置 jupyter notebook
再聊聊我常用的15个数据源网站
Trace tool for MySQL further implementation plan
【JokerのZYNQ7020】AXI_EMC。
Advanced learning of MySQL -- basics -- multi table query -- external connection
深度学习简史(一)
ZABBIX 5.0: automatically monitor Alibaba cloud RDS through LLD
[batch dos-cmd command - summary and summary] - view or modify file attributes (attrib), view and modify file association types (Assoc, ftype)
Attention SLAM:一种从人类注意中学习的视觉单目SLAM
Slow database query optimization
Building a dream in the digital era, the Xi'an station of the city chain science and Technology Strategy Summit ended smoothly
.class文件的字节码结构
Explain in detail the implementation of call, apply and bind in JS (source code implementation)
STM32开发资料链接分享
ActiveReportsJS 3.1中文版|||ActiveReportsJS 3.1英文版
Data sharing of the 835 postgraduate entrance examination of software engineering in Hainan University in 23
重上吹麻滩——段芝堂创始人翟立冬游记
Mujoco produces analog video
How do novices get started and learn PostgreSQL?
Use mujoco to simulate Cassie robot