当前位置：首页 > news >正文

dp_走方格（包含dfs分析，记忆化搜索）

news 2025/3/9 5:08:19

类似题目解析：dp_最长上升子序列（包含dfs分析，记忆化搜索）-CSDN博客

题目链接：2067. 走方格 - AcWing题库

题目图片：

分析题目（dfs）

这个题目说有一个行为n行，列为m列，在这个长方形里从左上角走到右下角，只能往右走，或者往下——》翻译过来就是一个二维数组的某个值f[i][j]只有两个选择——变成f[i+1][j]，或者变成f[i][j+1],求出方案数。（注意有个条件是不能走行号和列号同时为偶数的地方）

这种有多种选择题，显而易见先用dfs思考，

首先行号和列号同时为偶数——》选择不走

正常的——》可以选择走，也可以选择不走

到达最大值了——》也就是边界

上面就把dfs函数的具体思路分析出来了，下面展示代码——》

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;int n,m;int dfs(int x, int y) {if (x % 2 == 0 && y % 2 == 0) {return 0; // x和y均为偶数，无法移动，路径数为0}if (x == n && y == m) {return 1; // 到达终点，返回1条路径}int count = 0;if (x < n) count += dfs(x + 1, y);if (y < m) count += dfs(x, y + 1);return count;
}int main()
{scanf("%d%d",&n,&m);cout<<dfs(1,1);return 0;
}

上面代码其中的dfs函数就是按照一开始分析的方式写出来的，而先判断是不是都为偶数和先判断是不是到结尾点了的顺序不是很重要。

那么这个显而易见超时了，所以开始记忆化搜索优化——

记忆化搜索优化

▌核心思路：
在普通DFS中，若存在大量重复访问的相同状态参数组合，则需要用数组/哈希表存储该状态的答案，避免重复递归。

状态定义：将递归函数的所有可变参数（如坐标、剩余步长、标记位等）作为状态维度
（例：二维网格路径问题中，状态是坐标 (x,y)）
容器选择：优先用多维数组存储，若参数范围过大可用unordered_map等哈希结构

在递归函数的第一行检查当前状态是否已计算过（是否在数组里存储过），若存在缓存结果则直接返回，否则继续递归。

无论递归路径如何，在返回结果前必须将计算结果存入缓存容器。需特别注意：

所有分支都要存储结果（包括边界条件和中间状态）
存储时机：在计算完所有子状态后，通过mem[x][y] = result和return result来操作。

代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;
const int N=31;
int n,m;
int mem[N][N];int dfs(int x, int y) {if(mem[x][y])return mem[x][y];int p=0;if(x%2==0&&y%2==0){return 0;//这个不变成p=1是因为？//p=1 仅在到达终点时触发，表示找到一条合法路径。//而 x 和 y 均为偶数的坐标是非法停留点，此时没有任何合法路径能通过该点到达终点，因此必须返回 0。}if(x==n&&y==m){p=1;}if(x<n) p+=dfs(x+1,y);if(y<m) p+=dfs(x,y+1);mem[x][y]=p;return p;
}int main()
{scanf("%d%d",&n,&m);cout<<dfs(1,1);return 0;
}

dp

从记忆化搜索变成dp的核心规律：
记忆化搜索中的递归参数与动态规划的状态维度必须保持严格对应关系。记忆化搜索的dfs(a,b,c)参数表即对应动态规划的dp[a][b][c]状态定义。

其次，如果刚开始dfs是从开始的1，1推到n,m的，那dp就要从最后开始递推回去。

所以动态规划的二维数组的两个维度范围定了

是从n到1，另一个从m到1。

其中的公式思路和记忆化搜索里的dfs函数一样。

这个数组表示的是从这个位置开始到n,m这个位置（符合题意的）的方案数

代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;
const int N=31;
int n,m;
int f[N][N];int main()
{scanf("%d%d",&n,&m);//dpfor(int i=n;i>0;i--){for(int j=m;j>0;j--){if(i%2==0&&j%2==0){continue;}int p=0;if(i==n&&j==m){p=1;}if(i<n) p+=f[i+1][j];if(j<m) p+=f[i][j+1];f[i][j]=p;}}cout<<f[1][1]<<endl;return 0;
}