跳跃

小蓝在一个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列后，总的权值和最大。请问最大是多少？

输入描述

输入的第一行包含两个整数n,m，表示图的大小。
接下来 n 行，每行 m 个整数，表示方格图中每个点的权值。
其中，1 ≤ n ≤ 100，−10⁴ ≤ 权值 ≤ 10⁴。

输出描述

输出一个整数，表示最大权值和。

输入示例

3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4

输出示例

15

思路：动态规划

• 1，准备好一个空的二维数组dp，与map大小相同，用于DP，起点值初始化为map数组的起点值，其它初始化为负无穷(因为有负值)，
• 2，确定一个当前位置，更新DP数组中这个当前位置所能访问到的所有位置的值
• 3，遍历DP数组，使每一个格子都成为一次“当前位置”
• 4，则最后的答案就在DP数组的最后一格

如何更新：

• 1，以DP数组为遍历对象，map数组仅提供权值用于更新DP数组，改变的始终只有DP数组
• 2，遍历“当前位置”所能访问的所有位置，将“这些位置”(“当前位置”所能访问到的位置)的值与“当前位置”的值相加，并与“这些位置”对应的DP数组的值作比较，将DP数组的对应位置值更新为较大值
• 3，遍历DP数组，使每一个位置都成为“当前位置”，然后转2

代码如下：

#include <climits>
#include <iostream>
#include <vector>
using namespace std;//当前位置所能访问到的位置的增量数组
const int to[9][2] = {{1, 0}, {2, 0}, {3, 0}, {0, 1}, {1, 1},{2, 1}, {0, 2}, {1, 2}, {0, 3}};vector<vector<int>> map;  //权值数组
vector<vector<int>> v;    // DP数组
int n, m;                 //地图的行和列
int i, j;                 //临时变量//初始化，处理输入以及为DP做准备
void init() {scanf("%d%d", &n, &m);map.resize(n);v.resize(n);for (i = 0; i < n; i++) {map[i].resize(m);v[i].resize(m, INT_MIN);for (j = 0; j < m; j++) {scanf("%d", &map[i][j]);}}v[0][0] = map[0][0];  // DP数组第一个位置的初始化
}//解决问题
void solve() {int t_x = 0, t_y = 0;for (i = 0; i < n; i++) {for (j = 0; j < m; j++) {for (int k = 0; k < 9; k++) {t_x = i + to[k][0];t_y = j + to[k][1];if (t_x >= n || t_y >= m) continue;v[t_x][t_y] = max(v[t_x][t_y], v[i][j] + map[t_x][t_y]);}}}printf("%d\n", v[n - 1][m - 1]);  //输出DP数组的最后一个值(出口处的值)
}int main(void) {init();solve();return 0;
}