例一：求到终点的路径条数
思路：
深搜的时候是从vis[1][1]开始搜的，第一次直搜到vis[n][n]，然后返回的时候可以得到vis[n-1][n-2]那个点的路，当第二次搜到vi[n-1][n-2]这个点的时候就不用往下搜了， 直接加上在这个点的路。
代码：
lld dfs(int x, int y) {
if (vis[x][y] != 0) return vis[x][y]; //如果改点已搜过，直接返回结果即可
if (x == n && y == n) return 1;
for (int i = 0; i < 4; ++i) {
int nx = x + go[i][0];
int ny = y + go[i][1];
if (maze[nx][ny] != -1 && dist[nx][ny] < dist[x][y]) {
vis[x][y] += dfs(nx, ny);
}
}
return vis[x][y];
}
若没有使用记忆优化：
void dfs(int x,int y){
int sx,sy,i;
if(x==n&&y==n){
tot++;//tot记录能够到达终点的路的条数
return;
}
for(i=2;i<4;i++){
sx=x+dir[i][0],sy=y+dir[i][1];
if(sx>n||sy>n) continue;
if(dis[sx][sy]>=dis[x][y]) continue;
dfs(sx,sy);
}
}
例二：求不同的排列数
题意：用A~Z代替1~26，问一串数字有多少不同的译码种数。
关键：若下一位不为0，本位可以拆分出来则 ret += dfs(x + 1);。若本位和下一位不超过26，且再后面的一位不为0，则这两位可以拆分出来则 ret += dfs(x + 2);。
代码：
lld dfs(int s, int e) {
if (s >= e) return 1;
if (dp[s] > 0) return dp[s];
int t1 = str[s] - '0';
int t2 = str[s + 1] - '0';
if (t2 != 0) dp[s] += dfs(s + 1, e);
if (t1 * 10 + t2 <= 26 && str[s + 2] != '0') //只剩最后两位的时候可以再计算一次
dp[s] += dfs(s + 2, e);
return dp[s];
}
练习：