跳跃
题目描述
小蓝在一个 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^4 <= 权值 <= 10^4。
输出描述
输出一个整数，表示最大权值和。
输入输出样例
示例 1
输入
3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4
输出
15
运行限制
最大运行时间：1s
最大运行内存: 128M
分析
方法一：
dp函数方法，建议大家多用递归解决对学习dfs和bfs等等有很大裨益
关于解题：
其实之前一直用的LeetCode解题，对于这种输入输出都得自己写的方式还没缓过来,导致dp函数10分钟，修改错误30分钟。。。
关于代码：
dp有自顶向下，和自底向上的两种方法，对应递归和递推，我认为大家两种方法都得掌握，但我认为更重要的是递归的方法，因为这种方法容易写而且不容易犯小错误(当然得自己多写这种题，形成一种体系)，还有很重要的一点是递归方法在其他算法中运用也很多，你从dp开始就将递归慢慢掌握，有助于写dfs、bfs、回溯、贪心等等。
关于dp函数：
dp函数的结构(可结合代码画递归树理解)无非就是：
- 递归树的叶子结点的跳出条件->对应base case(决定子问题的深度(个数))、base case一般为最简单的题解子状态
- 递归函数的主体->对应状态转移方程(递归树的展开)
- 非叶子结点(子问题)的跳出条件->将return结果写在递归树展开的后面即可 总的过程：通过状态转移方程不断将递归树延伸，直到触及base case停止延伸，往前执行之前的递归，这样就完成了每个非叶子结点的结果跳出，最终得到题解。 但是用了这递归的方法会出现一个问题：递归树上可能大量结点重复计算，这个时候就需要一个备忘录一样的东西将以及计算好的题解保存，可将备忘录添加到base case中来，实际上我说的base case决定递归树的深度不完全正确，准确来说应该是决定子树的深度，因为递归过程实际上是一个入栈和出栈的过程，所以首先计算的是最深的那颗树。
讲了这么多，我来划一下重点：
- 递归的结构：
- base case (决定递归树深度，叶子结点的结果)
- 状态转移方程(决定递归树的延伸方式)
- 处理完子问题的返回(决定非叶子结点的处理结果)
- 递归的原理：
这方面也没办法讲的明白，递归实际上就是一个后进先出的栈的形式，即递归就是入栈和出栈的过程，根据递归树结合深搜理解是最好的。
提交答案
#include <bits/stdc++.h>
using namespace std;
int n,m;
int dp(vector<vector<int>>&grid,vector<vector<int>>&memo,int x,int y){
int dx[] = {0,0,0,-1,-1,-1,-2,-2,-3};//所有可能的步
int dy[] = {-1,-2,-3,0,-1,-2,0,-1,0};//所有可能的步
//base case:
if(x<0||y<0)return INT_MIN;
if(x==0&&y==0)return grid[0][0];
if(memo[x][y]!=INT_MIN)return memo[x][y];
//condition transfer:
int temp = INT_MIN;
for(int i=0;i<9;i++){
int q = dp(grid,memo,x+dx[i],y+dy[i]);
if(q==INT_MIN)continue;
temp = max(temp,q);
}//备忘录memo更新
memo[x][y] = temp + grid[x][y];
return memo[x][y];
}
int main()
{
cin>>n>>m;
//创建并赋值grid(方格)数组
vector<vector<int>>grid(n,vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>grid[i][j];
}
}
//调用dp函数解决问题：
vector<vector<int>> memo(n,vector<int>(m,INT_MIN));
cout<<dp(grid,memo,n-1,m-1);
return 0;
}
方法二：
#include <bits/stdc++.h>
using namespace std;
int n,m,ans,trans;
int main()
{
cin>>n>>m;
int grid[n+1][m+1];
int x[9] = {0,0,0,-1,-1,-1,-2,-2,-3};//所有可能的步
int y[9] = {-1,-2,-3,0,-1,-2,0,-1,0};//所有可能的步
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
cin>>grid[i][j];
int trans = INT_MIN;
for(int t=0;t<9;++t)
{
if(i+x[t]>0 && j+y[t]>0){
trans = max(trans,grid[i+x[t]][j+y[t]]);
}
}
if(trans!=INT_MIN) grid[i][j]+=trans;
}
cout<<grid[n][m]<<endl;
// 请在此输入您的代码
return 0;
}