類似題目解析：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;
}總結
這就是從dfs分析到記憶化搜索再到dp的方法，如果有進一步想學習，可以多練習幾道題，主頁有幾道類似的題目分析，可以點贊收藏去看一看。
