热门标签
热门文章
- 1vue-element-template/admin添加多标签(tags)功能和修改tags的背景颜色_修改背景颜色
- 2Oracle预定义的21个系统异常类型_oracle中有哪些预定义异常
- 3云计算项目五：部署数据库服务mysql ｜部署共享存储服务NFS ｜ 配置网站服务_mysql 如何使用共享存储
- 4去除二值化图像横向离散点
- 5C++程序的自启动写入注册表的代码_visual c++ 1.1.1 写入注册表自动运行
- 6【线性代数的几何意义】向量的基本几何意义
- 7【Shell 命令集合 系统管理 】⭐⭐Linux 显示系统的基本信息 uname命令 使用指南_uname()
- 82022年中国互联网行业人才需求趋势：技术类职能占比大，经济发达城人才需求大[图]_人才需求趋势图
- 9Unity的PlayerPrefs不起作用_unity playerprefs失效
- 10YOLOv8改进 | 损失篇 | VarifocalLoss密集目标检测专用损失函数 (VFLoss，原论文一比一复现)_yolov8论文
当前位置: article > 正文
一篇文章带你搞懂动态规划（由暴力递归到动态规划）
作者：IT小白 | 2024-02-16 22:38:38
赞
踩
一篇文章带你搞懂动态规划（由暴力递归到动态规划）
由递归到动态规划
思想
”动态规划“的过程相当于记忆化搜索， 即在普通递归的过程中用二维数组进行记忆化存储一些状态结果， 从而避免重复的计算（剪枝）。
举一个简单的例子：在
递归法求解斐波那契数列的过程中， 就进行了多次的重复计算， 而动态规划相当于是对已经计算的状态结果进行存储， 从而在调用的时候直接返回结果即可
f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n) = f(n - 1) + f(n - 2) f(n)=f(n−1)+f(n−2)
DP分析思路如下：
-
我们需要根据题意建立一个简单的暴力递归过程
-
所以这里，我们初步的优化思路：
在遍历到某一个状态时：
- 若是此状态已经在之前
算过， 那么直接返回结果即可 - 若是此状态之前
没算过， 那么调用递归函数进行计算， 并将状态记忆存储， 然后返回结果
- 具体记忆化存储状态的过程可以看成是一个打表填表的递推过程，由已有递归转移推未知来进行状态表的填充，从而转换为最终的DP
观看左神动态规划心得
文章会持续更新， 总结各种dp相关题型加入
具体题目:
一、机器人到达指定位置方法数
点击此处跳转：机器人达到指定位置方法数
一、暴力递归分析
#include <iostream> using namespace std; const int len = 5010; int process1(int cur, int rest, int aim, int N) { //cur:当前位置，需要走的步数， 目标位置， 位置数量 if (rest == 0) return cur == aim ? 1 : 0; if (cur == 1) return process1(cur + 1, rest - 1, aim, N); if (cur == N) return process1(cur - 1, rest - 1, aim, N); return process1(cur + 1, rest - 1, aim, N) + process1(cur - 1, rest - 1, aim, N); } int ways1(int N, int start, int K, int dest) { //位置数量， 开始位置，需要走的步数， 目的地位置 return process1(start, K, dest, N); } int main() { int N, M, K, P; cin >> N >> M >> K >> P; cout << ways1(N, M, K, P); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
二、《剪枝》记忆化存储
#include <iostream> #include <cstring> using namespace std; const int len = 5010; const int mod = 1e9 + 7; int N, M, K, P; int f[len][len]; int process1(int cur, int rest, int aim, int N, int f[len][len]) { //cur:当前位置，需要走的步数， 目标位置， 位置数量 if (f[cur][rest] != -1) return f[cur][rest]; int ans = 0; if (rest == 0) ans = cur == aim ? 1 : 0; else if (cur == 1) ans = process1(cur + 1, rest - 1, aim, N, f); else if (cur == N) ans = process1(cur - 1, rest - 1, aim, N, f); else ans = process1(cur + 1, rest - 1, aim, N, f) + process1(cur - 1, rest - 1, aim, N, f); f[cur][rest] = ans; return ans; } int ways1(int N, int start, int K, int dest) { //位置数量， 开始位置，需要走的步数， 目的地位置 memset(f, -1, sizeof f); return process1(start, K, dest, N, f); } int main() { cin >> N >> M >> K >> P; long long ans = (long long)ways1(N, M, K, P) % mod; cout << ans; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
三、递归转DP， 由状态方程打表
#include <iostream> #include <cstring> using namespace std; const int len = 5010; const int mod = 1e9 + 7; int N, M, K, P; int f[len][len]; int ways1(int N, int start, int K, int dest) { //位置数量， 开始位置，需要走的步数， 目的地位置 memset(f, 0, sizeof f); f[dest][0] = 1; for(int rest = 1; rest <= K; rest++) { f[1][rest] = f[2][rest - 1]; for(int cur = 2; cur < N; cur++) { f[cur][rest] = (f[cur-1][rest-1] + f[cur+1][rest-1]) % mod; } f[N][rest] = f[N - 1][rest - 1]; } return f[start][K]; } int main() { cin >> N >> M >> K >> P; int ans = ways1(N, M, K, P) % mod; cout << ans; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
二、排成一条线的纸牌博弈问题
点击此处跳转：排成一条线的纸牌博弈问题
第一步：暴力递归
代码如下：
#include <iostream> #include <algorithm> using namespace std; const int N = 5010; int a[N], n; int g(int a[], int L, int R); int f(int a[], int L, int R); //先手获得的最好分数返回 int f(int a[], int L, int R) { //若此时只剩一个数， 那么先手必定得到此数 if (L == R) return a[L]; //若是先手取左边， 则剩余的[L +1, R]只能作为后手 int p1 = a[L] + g(a, L + 1, R); //若是先手取右边， 则剩余的[L, R - 1]只能作为后手 int p2 = a[R] + g(a, L, R - 1); //先手选取对自己最优情况 return max(p1, p2); } //后手获得的最好分数返回 int g(int a[], int L, int R) { //若此时只剩一个数， 那么先手必定得到此数， 而后手就只能得到0 if(L == R) return 0; //若先手已经选取左边， 则此时后手在[L + 1, R]充当先手 int p1 = f(a, L + 1, R); //若先手已经选取右边， 则此时后手在[L, R - 1]充当先手 int p2 = f(a, L, R - 1); //因为决定权在于先手， 这里留给后手的只能是两种最优情况的较次者 return min(p1, p2); } //返回获胜者的分数 int win1(int a[]) { if (a == NULL || n == 0) return 0; int front = f(a, 0, n - 1); int back = g(a, 0, n - 1); return max(front, back); } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; cout << win1(a); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
这里可以看到普通的递归会直接超时
接下来进行记忆化存储状态， 省去重复计算步骤
- 1
第二步：递归转动态规划
这里的转换计算过程对应于：
这里进行初始化构建两个表：fmap 和 gmap 来存储状态， 进行优化， 分析取值范围， 在每次调用的时候加入两个表， 且在每次调用函数的时候返回当前状态值， 且如果没有计算过当前状态的话， 那么进行计算并更新此状态
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 5010; int a[N], n; //这里进行构建两个表分别来来存储先手和后手得分状态 int g(int a[], int L, int R, int fmap[][N], int gmap[][N]); int f(int a[], int L, int R, int fmap[][N], int gmap[][N]); //先手获得的最好分数返回 int f(int a[], int L, int R, int fmap[][N], int gmap[][N]) { if (fmap[L][R] != -1) return fmap[L][R]; int ans = 0; //若此时只剩一个数， 那么先手必定得到此数 if (L == R) ans = a[L]; else { //若是先手取左边， 则剩余的[L +1, R]只能作为后手 int p1 = a[L] + g(a, L + 1, R, fmap, gmap); //若是先手取右边， 则剩余的[L, R - 1]只能作为后手 int p2 = a[R] + g(a, L, R - 1, fmap, gmap); //先手选取对自己最优情况 ans = max(p1, p2); } //将答案存储，更新状态 fmap[L][R] = ans; return ans; } //后手获得的最好分数返回 int g(int a[], int L, int R, int fmap[][N], int gmap[][N]) { if (gmap[L][R] != -1) return gmap[L][R]; int ans = 0; //这里不需要考虑L==R情况，因为ans本身就等于0了 if (L != R) { //若先手已经选取L， 则此时后手在[L + 1, R]充当先手 int p1 = f(a, L + 1, R, fmap, gmap); //若先手已经选取R， 则此时后手在[L, R - 1]充当先手 int p2 = f(a, L, R - 1, fmap, gmap); //因为决定权在于先手， 这里留给后手的只能是两种最优情况的较次者 ans = min(p1, p2); } gmap[L][R] = ans; return ans; } //返回获胜者的分数 int win2(int a[]) { if (a == NULL || n == 0) return 0; //首先对"表"进行初始化， 若是某个状态还没有进行计算， 则赋值为 -1 int fmap[n][n], gmap[n][n]; memset(fmap, -1, sizeof fmap); memset(gmap, -1, sizeof gmap); int front = f(a, 0, n - 1, fmap, gmap); int back = g(a, 0, n - 1, fmap, gmap); return max(front, back); } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; cout << win2(a); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
此时的提交结果：
在这里有一个==细节==：
*二维数组作为函数参数*
规定：如果将二维数组作为参数传递给函数，那么在函数的参数声明中必须指明数组的列数，数组的行数没有太大关系，可以指定也可以不指定。因为函数调用时传递的是一个指针，它指向由行向量够成的一维数组。因此二维数组作为函数参数正确写法如下所示：
void Func(int array[3][10]);
void Func(int array[ ][10]);
但是不能把第二维或者更高维的大小省略，如下面的定义是不合法的：
void Func(int array[ ][ ]);
因为从实参传递来的是数组的起始地址，在内存中按数组排列规则存放(按行存放)，而并不区分行和列，如果在形参中不说明列数，则系统无法决定应为多少行多 少列，不能只指定一维而不指定第二维，下面写法是错误的：
void Func(int array[3][]);
第三步：状态转移打表
下半部分L < R都没用， 只需上半部分， 两个表互相关联，且通过对角线的两元素互相推
代码如下：
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 5010; int a[N], n; int win3(int a[]) { if (a == NULL || n == 0) return 0; int fmap[n][n], gmap[n][n]; //int front = f(a, 0, n - 1, fmap, gmap); //int back = g(a, 0, n - 1, fmap, gmap); //return max(front, back); for (int i = 0; i < n; i++) fmap[i][i] = a[i]; for (int j = 0; j < n; j++) gmap[j][j] = 0; //根据列（R）进行一步步计算推进，一个一个对角线进行赋值famp和gmap for (int startCol = 1; startCol < n; startCol++) { int L = 0; int R = startCol; while (R < n) { fmap[L][R] = max(a[L] + gmap[L + 1][R], a[R] + gmap[L][R - 1]); gmap[L][R] = min(fmap[L + 1][R], fmap[L][R - 1]); L++; R++; } } return max(fmap[0][n - 1], gmap[0][n - 1]); } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; cout << win3(a); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
最后的提交结果如下：
最后， 这里对于后手拿取的问题可以模拟下加深理解：
假设所给为[10, 20, 30]
后手会在两次最优中被动拿走较次的， 原因如下：
两种情况： 先手 - > 10， 后手 - > 30 || 先手 - > 30， 后手 - > 20
这里因为最优策略， 先手肯定会聪明的选取好的方案， 把较次的留给后手（20）
三、背包问题
点击此处跳转：01背包问题
在逐渐掌握后可以缩减为两步直接解决， 省去中间一步
第一步：递归模拟
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1010; int w[N], v[N], n, bag; int process(int w[], int v[], int index, int bag); int maxValue(int w[], int v[], int bag); int maxValue(int w[], int v[], int bag) { if(w == NULL || v == NULL || n == 0) return 0; return process(w, v, 0, bag); } //返回最大价值 int process(int w[], int v[], int index, int rest) { //重量、价值、当前位置、背包容量 if(index == n) return 0; if(rest < 0) return 0; //背包容量可以为0， 因为货物重量可能为0，而<0则为无效 //有货， index位置的货 //bag有空间 >= 0 //此时两种选择， 选 或 不选 //1.不要 int p1 = process(w, v, index + 1, rest); //2.要（判断是否装得下） int p2 = 0; if(rest >= w[index]) p2 = v[index] + process(w, v, index + 1, rest - w[index]); return max(p1, p2); } int main() { cin >> n >> bag; for(int i = 0; i < n; i++) { cin >> w[i] >> v[i]; } cout << maxValue(w, v, bag); //超时TLE return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
提交结果：
第二步：转DP
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1010; int w[N], v[N], n, bag; int dp(int w[], int v[], int bag) { if(w == NULL || v == NULL || n == 0) return 0; int dp[N][N]; for(int i = 0; i <= bag; i++) dp[n][i] = 0; for(int idx = n - 1; idx >= 0; idx--) { //这里每个状态只依赖下一行(idx + 1)的数据， 而和同行的无关， 故顺序都可 for(int rest = 0; rest <= bag; rest++) { //不取当前 int p1 = dp[idx + 1][rest]; //取当前 int p2 = 0; if(rest >= w[idx]) p2 = v[idx] + dp[idx + 1][rest - w[idx]]; dp[idx][rest] = max(p1, p2); } } return dp[0][bag]; //因为是从 n-1 递推到 0， 故 0 即为最终答案 } int main() { cin >> n >> bag; for(int i = 0; i < n; i++) cin >> w[i] >> v[i]; // cout << maxValue(w, v, bag); 上一步的会超时TLE cout << dp(w, v, bag); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
提交结果：
此题发现在构建dp表的时候， 两个变量 index （当前位置）和 bag（当前背包容量）， 每个状态只依赖于index + 1，而不依赖于同行其他， 故可以由二维数组继续优化为一维数组存储状态即可， 具体代码如下：
一维优化版：
#include<iostream> #include<algorithm> using namespace std; const int N = 1005; int f[N]; int main() { int n,m; cin >> n >> m; for(int i = 1;i <= n;i++) { int v,w; cin >> v >> w; for(int j = m;j >= v;j--) f[j] = max(f[j],f[j - v] + w); //容量为j时的最大价值 } cout << f[m] << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
提交结果：
四、数字字符串转换为字母组合的种数
点击链接跳转：数字字符串转换为字母组合的种数
题目如下：
思路：
考虑边界情况， 从 0 ~ n - 1位置进行遍历， 无需进行转换操作
- 若
i == str.length()， 则代表能跑通， 之前的遍历操作成立， 可构成一种方案数 - 若 在转换操作过程中遍历到单个
0，即此处跑不通， 断路不成
在判断完特殊情况后， 正常的 分为 i单转和 i & i+1组合转
i单转：成立那么直接进行下一个位置的操作，process(str, i + 1);组合转：若是可组成符合条件的组合， 那么直接进行第i + 2的位置的继续操作即可
第一步：递归
#include <iostream> #include <string> using namespace std; string str; // str[0...n-1]转换无需过问 // str[i...]去转换， 返回方案数 int process(string str, int i) { if (i == str.length()) return 1; //能到这儿说明之前都能跑通符合成立， 可构成一种方案数 if (str[i] == '0') return 0; //若是当前位置所指为'0'， 则代表跑不通 //str[i] ！= 0 //可能性一： i单转 int ways = process(str, i + 1); //成立那么直接操作下一个 //可能性二：i 与 i+1 进行组合 if (i + 1 < str.length() && ((str[i] - '0') * 10 + str[i + 1] - '0' < 27) ) { ways += process(str, i + 2); } return ways; } //str只含有[0, 9]， //返回多少种转换方案 int way1(string str) { if (str == "") return 0; return process(str, 0); //从下标为0开始递推 } int main() { cin >> str; cout << way1(str); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
第二步：转DP
观察尝试递归推导式可得：每个位置的状态依赖于后边的式子， 即填表需要从后往前依次递推转移
#include <iostream> #include <string> #include <cstring> using namespace std; const int mod = 1e9 + 7; string str; int dp(string str) { if(str == "") return 0; int N = str.length() + 1; int dp[N]; memset(dp, 0, sizeof dp); dp[N] = 1; //因为每个位置状态依赖于后边的， 故从后往前状态转移 for(int i = N - 1; i >= 0; i--) { if(str[i] == '0') dp[i] = 0; //可省略 else { int ways = dp[i + 1] % mod; if(i + 1 < str.length() && ((str[i] - '0') * 10 + str[i + 1] - '0' < 27) ) { ways += dp[i + 2] % mod; } dp[i] = ways; //更新表 } } return dp[0]; //因为是从后往前递推 } int main() { cin >> str; // cout << way1(str); cout << dp(str) % mod; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
提交结果：
后续更新ing
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/97363
推荐阅读
相关标签
