当看到“求方案总数”，“且当前决策只受上一个决策影响”的问题时，脑子里应该自动浮现这个框架：

long long dfs(int index, int last_state) {
// 1. 边界：任务完成了，算作 1 种有效方案
if (index > total_steps) return 1;
// 2. 累加器
long long res = 0;
// 3. 遍历当前所有可能的选择
for (int choice : all_possible_choices) {
// 4. 判断当前选择是否符合规则（依赖 last_state）
if (is_legal(choice, last_state)) {
// 5. 递归下去，把子问题的结果加起来
res += dfs(index + 1, choice);
}
}
return res;
}

​这种 DFS 其实就是自顶向下的动态规划。 dfs(col, prev_row)实际上就是在计算dp[col][prev_row]。 如果你在 DFS 里加上一个数组memo[col][prev_row]来记录已经计算过的结果（记忆化搜索），它就和递推形式的 DP 完全等价了。

一句话口诀： 按序搜，传状态，过边界，返一，合分求总数。

对于本题，传入的参数为当前的列号和上一行的行号，因为皇后也和上一个皇后在同一行或上下两行，所以要有上一行来作为参数 在主循环中主要是根据initial[i]即是否已经放了皇后来判断方案数

#include<bits/stdc++.h>
using namespace std;
int n;
int initial[11];
// col:当前列数
// prev_row:上一列皇后所在的行号
long long dfs(int col, int prev_row) {
    // 递归边界：所有列都放好了
    if(col>n) return 1;
    long long count=0;
    // 如果当前列已经有预设的皇后
    if (initial[col]!=0) {
        int curr_row = initial[col];
        // 如果是第一列，或者与上一列行数差不超过1
        if (col==1||abs(curr_row-prev_row) <= 1) {
            count+=dfs(col+1,curr_row);
        }
    } 
    // 如果当前列没有预设，需要尝试放置
    else {
        if (col==1){
            // 第一列可以放任何位置
            for(int r=1;r<=n;r++){
                count+=dfs(col+1,r);
            }
        } else {
            // 非第一列，只能放在上一列行号的[-1,0,1]范围内
            for(int r=prev_row-1;r<=prev_row+1;r++){
                if(r>=1&&r<=n) { //确保不越界
                    count+=dfs(col+1,r);
                }
            }
        }
    }
    return count;
}
int main() {
    while(cin>>n&&n!=0){
        for(int i=1;i<=n;i++){
            cin>>initial[i];
        }
        cout<<dfs(1,0)<<endl; //从第一列开始搜,初始行可以设为任意值
    }
    return 0;
}