动态规划入门

· · 题解

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

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

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

upt 2025/10/1：回答问题。笔者目前学业繁忙，可能看不见回复了，谅解！

第一阶段

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

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

需注意边界处理。

注意 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：第一份代码无法通过。只是方便读者学习暴力算法如何优化到正解。

Q：BFS 和递归行不行？

A：BFS 理论上也是可行的，直接递归是不可行的。实质上，这道题的解法都是解决大量重复，只是实现不同。

总结

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

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

做完这道题请你尝试：

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