[数据结构与算法]2021蓝桥杯模拟题 跳跃（DFS/动态规划）

?

该题我的第一思路是DFS,因为根据题意，我们要想找到到达终点的最大权值和，我们可以一个一个进行尝试，即从一个点出发，在所能走到的范围内进行搜索，直到到达终点，到达终点之后比较与其他走法所得到的权值和，从而得到最大权值和

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<algorithm>
#include<cmath>
#include<stack>
#include<iomanip>
#include<cstdio>
using namespace std;
typedef unsigned long long ll;

int n,m,MAXN=-100001;
int MAP[105][105];
int nextt[][2]={{0,1},{0,2},{0,3},{1,0},{2,0},{3,0},{1,1},{1,2},{2,1}};//能一步走到的地方

void dfs(int MAP[][105],int x,int y,int sum)
{
    if(x==n&&y==m)//到达终点
    {
        MAXN=max(MAXN,sum);//找最大值
        return ;
    }
    for(int i=0;i<9;i++)
    {
        int tx=x+nextt[i][0];
        int ty=y+nextt[i][1];
        if(tx<1||ty<1||tx>n||ty>m)//越界
        {
            continue;
        }
        sum+=MAP[tx][ty];//叠加权值
        dfs(MAP,tx,ty,sum);
        sum-=MAP[tx][ty];//返回的时候记得恢复
    }    
}

int main()
{
    int sum=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>MAP[i][j];
        }
    }
    sum+=MAP[1][1];//初始化
    dfs(MAP,1,1,sum);
    cout<<MAXN<<endl;
    return 0;
}

法2：动态规划

三步走入门动态规划之三步走??????

• 第一步定义dp[ i ][ j ]数组为从起点到下标为 （i，j）这个点的最大权值和
• 第二步找数组元素之间的关系式
• 第三步初始化

由于我们从一个点出发可以有以下这些地方可以走到

int nextt[][2]={{0,1},{0,2},{0,3},{1,0},{2,0},{3,0},{1,1},{1,2},{2,1}};//能一步走到的地方

所以dp[ i ][ j ]必然与这些点有关（即与能一步走到dp[ i ][ j ]的点）

我们可以据此写出伪代码

dp[i][j]=nums[i][j]+max(dp[i+nextt[z][0]],dp[j+nextt[z][1]]);（其中i>=0&&i<9） 

不过看到这个，心细的朋友可能有这样的疑惑：你这dp[ i ][ j ]都还没有赋值，哪来的

dp[i+nextt[z][0]] 和 dp[j+nextt[z][1]]

没错，确实，所以我们采用逆推的方法

?如图圆圈是我们的起点，正方形是我们能“一步”到达的地方

如果我们按照图中的方法去遍历是行不通的，因为

你这dp[ i ][ j ]都还没有赋值，哪来的dp[i+nextt[z][0]] 和 dp[j+nextt[z][1]]

所以我们采用

这样的方法来遍历，我们以正方形为起点，圆形则是能“一步”走到正方形的点

代码实现如下

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<algorithm>
#include<cmath>
#include<stack>
#include<iomanip>
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;

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){//寻找能“一步”到（i,j）的最大权值
          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;
}