一篇文章带你搞懂动态规划（由暴力递归到动态规划）
由递归到动态规划
目录
- 由递归到动态规划
- 思想
- 具体题目:
- 一、机器人到达指定位置方法数
- 一、暴力递归分析
- 二、《剪枝》记忆化存储
- 三、递归转DP， 由状态方程打表
- 二、排成一条线的纸牌博弈问题
- 第一步：暴力递归
- 第二步：递归转动态规划
- 第三步：状态转移打表
- 三、背包问题
- 第一步：递归模拟
- 第二步：转DP
- 一维优化版：
- 四、数字字符串转换为字母组合的种数
- 第一步：递归
- 第二步：转DP
- 五、拼词（困难，多想）
- 第一步：暴力递推
- 分析过程
- 第二步：记忆化存储
- 六、最长公共子序列
- 第一步：递归模拟
- 第二步：记忆化存储
- 代码1：
- 代码2：
- 七、最长回文子序列
- 解法一：
- 解法二：
- 第一步：递归
- 第二步：转DP
- 还可以优化， 位置依赖问题， 依赖的值有：
- 八、棋盘走马类型
- 一：递归
- 二、转DP
- 相关题目：[ 骑士在棋盘上的概率](https://leetcode.cn/problems/knight-probability-in-chessboard/)
- 九、蜗牛
- 十、松散子序列
- 解法一：==状态机==DP分析法
- 解法二：线性DP分析法
- 十一、保险箱
- 解法一：
- 解法二：
- 后续更新ing
思想
”动态规划“的过程相当于记忆化搜索， 即在普通递归的过程中用二维数组进行记忆化存储一些状态结果， 从而避免重复的计算（剪枝）。
举一个简单的例子：在递归法求解斐波那契数列的过程中， 就进行了多次的重复计算， 而动态规划相当于是对已经计算的状态结果进行存储， 从而在调用的时候直接返回结果即可
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 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 //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 //位置数量， 开始位置，需要走的步数， 目的地位置 memset(f, 0, sizeof f); f[dest][0] = 1; for(int rest = 1; rest f[1][rest] = f[2][rest - 1]; for(int cur = 2; cur > M >> K >> P; int ans = ways1(N, M, K, P) % mod; cout //若此时只剩一个数， 那么先手必定得到此数 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 > a[i]; cout 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 > a[i]; cout 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; for (int i = 0; i > a[i]; cout 10， 后手 - > 30 || 先手 - > 30， 后手 - > 20这里因为最优策略， 先手肯定会聪明的选取好的方案， 把较次的留给后手（20）
三、背包问题
点击此处跳转：01背包问题
在逐渐掌握后可以缩减为两步直接解决， 省去中间一步
第一步：递归模拟
#include #include #include 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 = 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 > w[i] >> v[i]; } cout if(w == NULL || v == NULL || n == 0) return 0; int dp[N][N]; for(int i = 0; i //这里每个状态只依赖下一行(idx + 1)的数据， 而和同行的无关， 故顺序都可 for(int rest = 0; 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 > w[i] >> v[i]; // cout int n,m; cin n >> m; for(int i = 1;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 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; // cout if(i == 0 && j == 0) return str1[i] == str2[j] ? 1 : 0; else if(i == 0) { if(str1[i] == str2[j]) return 1; else return process1(str1, str2, i, j - 1); } else if(j == 0) { if(str2[j] == str1[i]) return 1; else return process1(str1, str2, i - 1, j); } else { // i != 0 && j != 0 // 不考虑 i, 可能考虑j int p1 = process1(str1, str2, i - 1, j); // 不考虑 j, 可能考虑i int p2 = process1(str1, str2, i, j - 1); // 此时刚好 i 所在 与 j所在 对应匹配， 匹配 或 都不考虑 int p3 = str1[i] == str2[j] ? 1 + process1(str1, str2, i - 1, j - 1) : 0; return max({p1, p2, p3}); } } int longestCommonSubsequence(string text1, string text2) { if(text1 == "" || text2 == "") return 0; return process1(text1, text2, n - 1, m - 1); } public: int dp[10001][1001]; int longestCommonSubsequence(string text1, string text2) { if(text1 == "" || text2 == "") return 0; int n = text1.length(); int m = text2.length(); memset(dp, 0, sizeof dp); dp[0][0] = text1[0] == text2[0] ? 1 : 0; for(int i = 1; i
-
文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。
