文章目录
一、前言
二、AcWing 1015. 摘花生
1.题目
2.逻辑解释
3.AC代码
三、AcWing 1018. 最低通行费
1.题目
2.逻辑解释
3.AC代码
四、AcWing 1027. 方格取数
1.题目
2.逻辑解释
3.AC代码
五、AcWing 275. 传纸条
1.题目
2.逻辑解释
3.AC代码
一、前言
AcWing算法提高课内容，本文讲解 动态规划
本篇包括以下题目：
AcWing 1015. 摘花生
AcWing 1018. 最低通行费
AcWing 1027. 方格取数
AcWing 275. 传纸条
写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来，博主会立即改正！望大家海涵
二、AcWing 1015. 摘花生
1.题目
本题链接：摘花生
本博客提供本题截图：
2.逻辑解释
拿到一个题目后，我们分为两步去考虑这个问题：
第一步： 把题目进行抽象：其实就是对于一个矩形，我们从它的左上角走到右下角，每一个点上都一个数值，走到一个点后就加上这个点的值，每次只能往右走或者往下走，问走到右下角的话，数值的累计最大值是多少。
第二步： 进行dp分析：比如我们现在在[i, j]这个点上，dp的关键就是分析这个点可以由哪个点转换而来：显然，对于这个点而言，根据题意可以由上面的一个点转换，亦可由左边的一个点转换过来，而我们的需求为最大值，故我们可以得到状态转移方程：f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];
3.AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 110; int w[N][N]; int f[N][N]; int main() { int t; cin >> t; while (t -- ) { int r, c; cin >> r >> c; for (int i = 1; i <= r; i ++ ) for (int j = 1; j <= c; j ++ ) cin >> w[i][j]; for (int i = 1; i <= r; i ++ ) for (int j = 1; j <= c; j ++ ) f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j]; cout << f[r][c] << endl; } return 0; }
三、AcWing 1018. 最低通行费
1.题目
本题链接：最低通行费
本博客提供本题截图：
2.逻辑解释
拿到一个题目后，我们分为两步去考虑这个问题：
第一步： 把题目进行抽象：其实就是对于一个矩形，我们从它的左上角走到右下角，每一个点上都一个数值，走到一个点后就加上这个点的值，每次只能往右走或者往下走，问走到右下角的话，数值的累计最小值是多少。
第二步： 进行dp分析：比如我们现在在[i, j]这个点上，dp的关键就是分析这个点可以由哪个点转换而来：显然，对于这个点而言，根据题意可以由上面的一个点转换，亦可由左边的一个点转换过来，这里或许你会考虑：那么边界情况是否需要我们特判呢？即当我们的i或者j等于1的时候，需要特判，这个题和上一个题的区别就有了，因为我们的数组是从下标1开始的，而因为我们数组为全局定义，i = 0和j = 0的点的值是默认为0的，而我们的需求为最小值，故我们需要去特判，故我们可以得到状态转移方程：
if (i != 1 && j != 1) f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j]; else if (i == 1) f[i][j] = f[i][j - 1] + w[i][j]; else f[i][j] = f[i - 1][j] + w[i][j];
3.AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 110; int w[N][N]; int f[N][N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) cin >> w[i][j]; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i != 1 && j != 1) f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j]; else if (i == 1) f[i][j] = f[i][j - 1] + w[i][j]; else f[i][j] = f[i - 1][j] + w[i][j]; cout << f[n][n] << endl; return 0; }
