部分和问题

//Input
int a[MAX_N];
int n, k;

//已经从前i项得到了和 sum, 然后对于 i 项之后的进行分支
bool dfs(int i, int sum) {
  // 如果前n项都计算过了， 则返回 sum 是否与 k相等
  if(i == n ) return sum == k;
  
  //不加上 a[i] 的情况
  if(dfs(i+1,sum)) return true;
  
  //加上 a[i] 的情况
  if(dfs(i+1,sum + a[i])) return true;
  
  // 无论是否加上 a[i] 都 不能凑成k 就返回 false
  return false;
}
void solve(){
  if(dfs(0,0)) printf("Yes\n");
  else printf("Nn\n");
}

POJ 2386 数水洼

题意：

1. 给出map, 数水洼的个数

//Input
char map[MAX_N][MAX_N];
int N, M;//N行 列

while(scanf("%d%d", &N, &M)!=EOF){
  for(int i = 1; i <= N;i++){
    for(int j = 1; j <= M; j++){
      printf("%c", map[i][j]);
    }
  }
}

// 选一个点W"开始, 往8个方向走，如果为'W' ,先把它变为 '.' 再以新的点为中心，一直到无路可走，就算一个水洼；（状态转移：点 --> 点）

void count_shuiwa(int point_x, int point_y){	//调用一次就会摧毁一个水洼
  	
    int dx[10] ={-1,0,1,-1,1,-1,0,1} ;
    int dy[10] ={-1,-1,-1, 0, 0, 1, 1,1};
    for(int i = 0; i < 8; i++){
      int next_x = point_x + dx;
      int next_y = point_y + dy;
      if((next_x>=1&&next_x <= M)&&(next_y>=1 && next_y <= N) && map[next_y][next_x]=='W'){
        map[next_y][next_x] = '.';	//放到函数开头就可以了；
        count_shuiwa(next_x,next_y);
      }
    }
  return ;
}
number++;

//注：上述算法存在一个问题，就是起点的'W' 不会被变为 '.';

写深搜的关键点

1. ​

补背景知识

1. 递归

Hanoi 问题：

心得：

• 一般的解题思路是综合法，即正推，但递归思维确实分析法，即逆推。
• 递归是靠逐级向下一级的调用栈求资源实现的，所以要写好递归基和递归操作对应的状态变化
• 对算法得正确性要有充分信任和把握。不然写错了就无从下手了。

N 皇后问题：

心得：

• 这个给人的感觉更像递归，也许是因为看起来更像从k =0开始的；
• 最后发现其实是对多重循环的实现；

逆波兰表达式

心得：

爬楼梯：

心得：

• 注意递归基的写法；

count24

心得：

• 虽然是抄他人的代码，但还是调试了半个小时左右，原因是if的判断条件后直接加了分号；

判断能否到终点的深度搜素算法

//1. 单纯判断能否到达终点， 不记录路径
bool Dfs(V){
  if( V 为 终点)
    	return	 true;
  if( v 为旧点)
    	return false;
  将V 标记为旧点；
   对和V相邻的每个节点 U{
    if(Dfs(U) == true)
       return true;
  }
  return false;
}

int main(){
  将所有点都标记为新点；
     起点= 1；
    终点 = 8；
    cout << Dfs(起点)；
}

// 2. 判断从 V 出发是否能到达终点， 要记录路径；

Node path[MAX_LEN];	//MAX_LEN 取节点总数即可；
int depth;
bool Dfs(V){
  if(V 为终点){
    path[depth] = V;
    return true;
}
  if(V 为旧点)
     return false;
  将V标记为旧点；
  path[depth] = V;
  ++depth; //?
  对和 V 相邻的每个节点 U{
    if(Dfs(U)==true)
      return true;
  }
  --depth;	// ?
  return false;
  
  int main(){
    将所有点都标记为新点；
      depth = 0;
    if(Dfs(起点)){
      for(int i = 0; i <= depth ; i++)
        cout << path[i] << endl;
    }
  }

图的表示方法

1. 邻接矩阵：用一个二维数组G存放图， G[i][j] 表示节点 i 和节点 j 之间边的情况（如有无边， 边方向， 权值的大小）
2. 邻接表， 一维向量，（其实就是省去了不连接的情况）

数城堡问题：

关于极大连通子图：往里头加任何一个图里的其它点，就会变得不连通，那么这个图就是极大连通子图。

数城堡：

• 要分清楚哪些任务应放在dfs函数里面做，哪些任务应放在函数外面做；