The Subset Sum Problem

//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: Counting Ponds

Problem:

1. Given a map, count the ponds.

//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' 不会被变为 '.';

Key Points When Writing DFS

1. ​

Background Knowledge

1. Recursion

Tower of Hanoi:

Notes:

• The usual approach is synthesis, or forward reasoning, while recursive thinking uses analysis, or backward reasoning.
• Recursion obtains resources through successive calls down the call stack, so get the base case and the state changes for each recursive operation right.
• Understand why the algorithm is correct and trust that reasoning. Otherwise, you will not know where to start when something goes wrong.

N Queens Problem:

Notes:

• This feels more like recursion, perhaps because it seems to start from k =0.
• In the end, I realized it is actually an implementation of nested loops.

Reverse Polish Notation

Notes:

Climbing Stairs:

Notes:

• Pay attention to how the base case is written.

count24

Notes:

• Although I copied someone else’s code, I still spent about half an hour debugging it because I had put a semicolon directly after the if condition.

A Depth-First Search Algorithm for Checking Whether the Destination Is Reachable

//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;
    }
  }

Ways to Represent a Graph

1. Adjacency matrix: store the graph in a two-dimensional array G. G[i][j] represents the edge between nodes i and j, such as whether it exists, its direction, and its weight.
2. Adjacency list: a one-dimensional vector, essentially leaving out entries for unconnected nodes.

The Castle-Counting Problem:

On maximal connected subgraphs: if adding any other vertex from the graph makes the subgraph disconnected, it is a maximal connected subgraph.

Counting Castles:

• Be clear about which tasks belong inside the dfs function and which belong outside it.