【蓝桥杯2021模拟赛】【动态规划】跳跃（超详解+原理分析）
目录
题目
小蓝在一个 n 行 m 列的方格图中玩一个游戏。
开始时，小蓝站在方格图的左上角，即第 1 行第 1 列。
小蓝可以在方格图上走动，走动时，如果当前在第 r 行第 c 列，他不能走到行号比 r 小的行，也不能走到列号比 c 小的列。同时，他一步走的直线距离不超过 3。
例如，如果当前小蓝在第 3 行第 5 列，他下一步可以走到第 3 行第 6 列、第 3 行第 7 列、第 3 行第 8 列、第 4 行第 5 列、第 4 行第 6 列、第 4 行第 7 列、第 5 行第 5 列、第 5 行第 6 列、第 6 行第 5 列之一。
小蓝最终要走到第 n 行第 m 列。
在图中，有的位置有奖励，走上去即可获得，有的位置有惩罚，走上去就要接受惩罚。奖励和惩罚最终抽象成一个权值，奖励为正，惩罚为负。
小蓝希望，从第 1 行第 1 列走到第 n 行第 m 列后，总的权值和最大。请问最大是多少？
题目链接
跳跃 - 蓝桥云课 (lanqiao.cn)
https://www.lanqiao.cn/problems/553/learning/
输入描述
输入的第一行包含两个整数 n, m 表示图的大小。
接下来 n 行，每行 m 个整数，表示方格图中每个点的权值。
其中，1 <= n <= 100，-10^4 <= 权值 <= 10^4。
输出描述
输出一个整数，表示最大权值和。
测试样例
输入样例
3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4输出样例
15提交结果截图
详细分析
1.【分析题目】如下表所示，按题目中所述，我们将从（1,1）号格子能够一跳跃次到达的格子标记上‘ 1 ’，可以看出，这是一个三角形区域，从这个角度出发，我们很难想到解法。
2.【逆向思考】我们不妨换个角度思考，我们既然要求走到（n，m）号格子的总的最大权值和，那么我们就应该想想，从哪些格子能够走到某目标格子。如下图所示，我们将（5,5）号格子标记为目标格子，将能够一次跳跃到达（5,5）号格子的格子标记上‘ 1 ’，我们可以发现它还是一个三角形。
3.【找到规律】那么如果仔细观察就可以发现，所有可以一次跳跃到达该格子的格子都在该格子的左上部分区域，那么我们只需要将目标格子的左上部分区域的格子的F值（设F值为到达一个格子的最大总权值和）求出，即可将目标格子的F值确定下来。
4.【动态规划思想】如下表所示，只要我们按照A~Y的顺序 （即从左往右、从上往下）得到每个格子的F值，仅需要遍历一遍每个格子，当遍历到最后一个格子时，即可得到最后一个格子的F值。
5.【分析原理】为什么这样做是对的呢？
这就涉及到的动态规划的性质了（下面一段来自百度百科）
-
最优化原理（最优子结构性质）
最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质
在这个题目中子问题就是，求出前面的格子的F值，而前面的格子的F值又受到前面的格子的前面的格子的影响（子问题重叠性质），所以必须保证每一步求出的F值都是正确的，这样才能保证下一步得到的结果的正确性！
而因为我们之前推过，所有可以一次跳跃到达该格子的格子都在该格子的左上部分区域，所以我们按照A~Y（即从左往右、从上往下）的顺序 走的话，其实计算每个格子的F值时，其左上部分区域的F值都已经求出来了！所以由此可知我们最后求得的结果是正确的！
带详细注释的源代码
#include <iostream>
#include <algorithm>
#include "string.h"
#include <climits>
#include <vector>
using namespace std;
int n, m;
vector< vector<int> >weight(101);//每个点的权值
vector< vector<long long> >totoal_weight(101);//存储走到每个点的最大权值和
long long find_max(int x, int y)//找到走到该点的所需的最大权值和（不包括该点的权值）
{
long long max = LLONG_MIN;
for (int i = x; i >= 1; i--)//从该点往上
{
for (int j = y; j >= 1; j--)//从该点往左
{
//1.不能原地踏步，所以不能与该点坐标一样
//2.步数要小于等于3
//3.要比当前的max大才更新max
if (!(x == i && y == j) && (x - i + y - j) <= 3 && max < totoal_weight[i][j])
max = totoal_weight[i][j];
}
}
if (max == LLONG_MIN)//说明是起点，返回0即可
return 0;
else //返回走到该点所需的最大权值和（不包括该点的权值）
return max;
}
int main()
{
cin >> n >> m;
int w;//临时变量，某点的权值
for (int i = 1; i <= n; i++) //行输入
{
weight[i].push_back(0); //占位，因为j要从1开始，而数组下标从0开始
totoal_weight[i].push_back(0); //占位
for (int j = 1; j <= m; j++) //列输入
{
cin >> w;
weight[i].push_back(w);
totoal_weight[i].push_back(w);
}
}
for (int i = 1; i <= n; i++) //从上往下
{
for (int j = 1; j <= m; j++) //从左往右
{
totoal_weight[i][j] += find_max(i, j);//得到每个点的最大权值和
}
}
cout << totoal_weight[n][m] << endl; //输出最后一个点的最大权值和
return 0;
}