蓝桥杯：跳跃 ← 深搜（dfs）或动态规划（dp）_dfs动态规划

【题目来源】
https://www.lanqiao.cn/problems/553/learning/

【题目描述】
小蓝在一个 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。

【输出描述】
输出一个整数，表示最大权值和。

【输入样例】
3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4

【输出样例】
15

【算法分析】
一、深度优先搜索法
● 深度优先搜索（dfs）算法模板：https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● 据题意，每次只能往右或往下走，且一步走的直线距离不超过 3，故有 9 种走法。这 9 中走法分别为：(0,1)、(0,2)、(0,3)、(1,0)、(1,1)、(1,2)、(2,0)、(2,1)、(3,0)。在代码中，可设 x 坐标增量 dx 及 y 坐标增量 dy 分别为：dx[]={0,0,0,1,1,1,2,2,3} 及 dy[]={1,2,3,0,1,2,0,1,0}


二、动态规划法
● 动态规划求解的最后一步法：https://blog.csdn.net/hnjzsyjyj/article/details/112797538
● 据题意，每次只能往右或往下走，且一步走的直线距离不超过 3，故有 9 种走法。这 9 中走法分别为：(0,1)、(0,2)、(0,3)、(1,0)、(1,1)、(1,2)、(2,0)、(2,1)、(3,0)。显然，此题适用于利用动态规划求解。故利用最后一步法分析，设状态 f[i][j] 表示从第 1 行第 1 列走到第 i 行第 j 列后的最大权值和，可得状态转移方程为 f[i][j]=max(f[i][j-k],f[i-k][j])，其中k∈[1,3]。
● 题目中 1<= n <=100，且只能往右或往下走，故必有 1<= m <=100。依据上面分析，在代码中，可设 x 坐标增量 dx 及 y 坐标增量 dy 分别为：dx[]={0,0,0,1,1,1,2,2,3} 及 dy[]={1,2,3,0,1,2,0,1,0}
● 

【算法代码：dfs】

#include <bits/stdc++.h>
using namespace std;
 
const int maxn=105;
int imap[maxn][maxn];
 
int ans=0;
int n,m;
int dx[]= {0,0,0,1,1,1,2,2,3};
int dy[]= {1,2,3,0,1,2,0,1,0};
 
void dfs(int x,int y,int t) {
    int sum=t+imap[x][y];
    if(x==n && y==m) {
        if(sum>ans) ans=sum;
        return;
    }
 
    for(int i=0; i<9; i++) {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx<1 || nx>n || ny<1 || ny>m) continue;
        dfs(nx,ny,sum);
    }
    return;
}
 
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>imap[i][j];
 
    dfs(1,1,0);
    cout<<ans<<endl;
}
 
/*
in:
3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4
out:
15
*/

【算法代码：动态规划】

#include <bits/stdc++.h>
using namespace std;
 
const int maxn=105;
int a[maxn][maxn];
int f[maxn][maxn];
 
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin>>a[i][j];
        }
    }
 
    f[1][1]=a[1][1];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            for(int k=1; k<=3; k++) {
                if(i-k>=1) f[i][j]=max(f[i][j],f[i-k][j]+a[i][j]);
                if(j-k>=1) f[i][j]=max(f[i][j],f[i][j-k]+a[i][j]);
            }
        }
    }
 
    cout<<f[n][m]<<endl;
 
    return 0;
}
 
/*
in:
3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4
out:
15
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/112797538
https://blog.csdn.net/qq_74156152/article/details/133833258
https://blog.csdn.net/CH_canghan/article/details/131032526
https://blog.csdn.net/NOT_TODAY1/article/details/120907710
https://blog.csdn.net/hnjzsyjyj/article/details/114408491