自动搬运

查看原文

来自洛谷，原作者为

	da_ke INTP | 路漫漫其修远兮，吾将上下而求导

搬运于2025-08-24 22:41:38，当前版本为作者最后更新于2023-05-11 20:06:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

upt 2023/7/21：增加一些内容。

upt 2024/3/17：解答一些问题，删了一些废话。

upt 2024/8/27：补充了一个模板。

第一阶段

我不会动态规划 dp，我只会深度优先搜索 DFS。

我们先按二维数组的习惯构建坐标系。$(x,y)$ 表示第 $x$ 行，第 $y$ 列。

需注意边界处理。

• 走到第 $n$ 行第 $m$ 列时，证明我们已经走到了终点，所以增加 $1$。

• 如果越界了，那么就不算。

• 如果走到了题目中规定不走的格子，那么也不算。

注意 if 条件判断的顺序不能错哟。（请读者仔细考虑）

边界处理完后，我们看看怎么递归。

如果我们记 $f_{x,y}$ 为点 $(x,y)$ 到终点走法总数，依据题意可得

$$f_{x,y}=f_{x+1,y}+f_{x,y+1}$$

其中 $f_{x+1,y}$ 表示 向下走一步后到终点走法总数，$f_{x,y+1}$ 表示 向右走一步后到终点走法总数。

如上所述递归即可。

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n,m;

int dfs(int x,int y){
    if(x>n||y>m) //如果越界了,那么就不算.
        return 0; 
    if(x==n&&y==m) ////走到第 n 行第 m 列时,证明我们已经走到了终点,所以增加 1 .
        return 1;
    if((x%2==0)&&(y%2==0)) //如果走到了题目中规定不走的格子,那么也不算.
        return 0; //注意if的顺序不能错哟
    int ans=dfs(x+1,y)+dfs(x,y+1); //递归求解
    return ans; //返回答案
}

signed main(){
    cin>>n>>m;
    cout<<dfs(1,1);
}

建议读者仔细理解上面程序。

时间复杂度： 指数级别的。

统一回复一下：上面的 DFS 无法通过此题。因为其时间复杂度与普通的 DFS 没有任何区别，只是将答案设置为了递归函数的返回值。

第二阶段 (记忆化搜索)

关键词： 记忆化搜索

类似 P1048，我们也可以通过添加记忆化数组来优化算法。

#include <bits/stdc++.h>

using namespace std;

int n,m;
int mem[100][100]; //记忆化

int dfs(int x,int y){
    if(x>n||y>m)
        return 0;
    if(x==n&&y==m)
        return 1;
    if((x%2==0)&&(y%2==0))
        return 0;
    if(mem[x][y]!=-1)
        return mem[x][y];
    int ans=dfs(x+1,y)+dfs(x,y+1);
    return mem[x][y]=ans;
}

signed main(){
    memset(mem,-1,sizeof(mem)); //记得清空为-1
    cin>>n>>m;
    cout<<dfs(1,1);
}

时间复杂度：$O(nm)$。（每个函数调用只访问了一次）

模板总结

其实我之前的那种写法不太好调试，这里给一个刘汝佳老师推荐的写法模板：

// 这里是一个二维 DP 模板，其他可以类推。
int mem[N][N];
int dp(int i,int j)
{
  int& ans=mem[i][j]; // 传引用，不会自己百度
  if(ans!=-1) return ans; // 记忆化
  ans=min(...) // ... 填转移方程。
  return ans; // 返回，实际上也实现了记忆化。
}
memset(mem,-1,sizeof(mem));

问题&解答

Q chuiniudawang：return mem[x][y]=ans; 的作用是什么，为什么不直接return ans;。

A da_ke：return mem[x][y]=ans; 的作用是先 mem[x][y]=ans，再 return mem[x][y]；若直接 return ans; 则相当于没有「记忆化」，会超时。

Q xyx2002：时间超出了。

A da_ke：如果你提交第一份当然会超时，因为它没有剪枝。设想一下，第一份代码就是普通的 DFS，复杂度自然是指数级别的。

Q：dfs过不了。

A：第一份代码无法通过。只是方便读者学习暴力算法如何优化到正解。

总结

这道题让我们学会了 记忆化搜索 这个法宝。用记忆化搜索会使代码比递推自然。

记忆化的关键是要大胆搜索，小心判断边界。

做完这道题请你尝试：

• P1464 Function（提示：不要每次都清空记忆数组）

• P1002 过河卒（提示：注意边界哟）

这是蒟蒻的第一篇题解，感谢支持！