基本思想
第一次学习dfs的同学也许像我一样,刚开始学习的时候,感觉在写dfs不知道要干些什么.
首先我们要知道dfs和bfs,一种是深度优先搜索,一种是广度优先搜索.
深度优先遍历只要前面有路,就会一直往前走,直到无路可走才会回头.
做这类形的题最主要的是不知道该如何写dfs方法.
dfs首先想的是递归的终止条件,返回值以及边界条件,还有根据题目不同给出的不同判断条件.
dfs方法本身是递归,递归的思想是我根据某种条件来逐渐深入搜索,条件是十分重要的.
同时dfs的题中也会用到剪枝和回溯的思想.
dfs模板
static int n,m;
static int[][] map;
static booelan[][] isg;
static int[][] lujin = {{1,0},{-1,0},{0,1},{0,-1}};
static void dfs(int t,int x,int y) {
vis[x][y] = t;
isg[x][y]=true;
for(int i=0;i<4;i++)
if(x<0&&y<0&&x>map.length&&y>map[0].length$$!isg[x][y]){
dfs(t,x+lujin[i][0],y+lujin[i][1]);
}
}
蓝桥javab组数字三角形
试题 H: 数字三角形（20分）
【问题描述】
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。 对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最 大的和。
路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。
【输入格式】
输入的第一行包含一个整数 N (1 < N ≤ 100)，表示三角形的行数。下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。
【输出格式】
输出一个整数，表示答案。
【样例输入】
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【样例输出】
27
思路
首先看完这道题我们能得到以下几条信息
- 遍历的时候只能向左下,右下走
- 向左下走的次数与向右下走的次数相差不能超过 1,这个是整体的向左下走的次数与整体向右走的次数.
- 返回的是最后走到底时的最大数值.
现在开始设计dfs, 最重要的是要思考首先我们让其(0,0)点开始,首先我们考虑
结束条件就是当遍历到底层,以及向左和向右的次数的差值为1
if(x=n-1&&Math.abs(left-right)==1)
第二考虑返回值, 这里我们要找到的是最大值,我们需要比较递归后返回的数值
Math.max(maxx,max1);
第三个我考虑的dfs方法的参数,这个参数的设置之前一直比较困扰我,我什么时候需要带参数,什么时候不需要带参数.
我觉的应该是要把在递归中需要比较判断的参数放入dfs方法中.
这里需要有的参数
public static void dfs(int x,int y ,int left,int right,int max1){}
接下来我们向下遍历的时候我们要考虑边界问题.
if (xx>=1 && xx<=n && yy>=1 && yy<=xx && vis[xx][yy]==0) {
这个题涉及到了回溯,回溯的思想是搜索一个问题的一个解或者 所有解 的方法。在求解的过程中，如果继续求解不能得到题目要求的结果，就需要 回退 到上一步尝试新的求解路径。
这里的vis[][]用来判断当前节点是否已经走过了.
接下来考虑剪枝,
vis[xx][yy] = 1;
if (i==0) left++;
else right++;
dfs(xx,yy,left,right,sum+num[xx][yy]);
vis[xx][yy] = 0;
if (i==0) left--;
else right--;
代码
import java.util.Scanner;
public class Main {
static int n;
static int[][] dir = {{1,0},{1,1}};
static int[][] num,vis;
static int maxx;
static void dfs(int x,int y,int left,int right,int sum) {
if (x==n && Math.abs(left - right) <= 1) {
maxx = Math.max(maxx, sum);
return;
}
for (int i=0;i<2;i++) {
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if (xx>=1 && xx<=n && yy>=1 && yy<=xx && vis[xx][yy]==0) {
vis[xx][yy] = 1;
if (i==0) left++;
else right++;
dfs(xx,yy,left,right,sum+num[xx][yy]);
vis[xx][yy] = 0;
if (i==0) left--;
else right--;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
num = new int[n+1][n+1];
vis = new int[n+1][n+1];
for (int i=1;i<=n;i++) {
for (int j=1;j<=i;j++) {
num[i][j] = sc.nextInt();
vis[i][j] = 0;
}
}
vis[1][1] = 1;
maxx = num[1][1];
dfs(1,1,0,0,num[1][1]);
System.out.println(maxx);
}
}
