算法思想之深度优先搜索（DFS）、递归以及案例（最多能得到多少克黄金、精准核酸检测、最富裕的小家庭）

深度优先搜索（DFS）、递归

• 深度优先搜索（Depth First Search，DFS）是一种用于遍历或搜索树或图的算法。在 DFS 算法中，从起始节点开始，沿着一条路径尽可能深地访问节点，直到到达叶子节点或者无法继续前进为止。然后退回到最近的一个有未探索节点的分支节点，继续探索其他路径，直到所有节点都被访问过为止。
• 深度优先搜索常常用于解决以下类型的问题：深度优先搜索是一种简单而强大的算法，可以解决许多实际问题。
  • 图遍历：在无向图或有向图中寻找特定节点之间的路径、判断图的连通性等。
  • 连通性问题：判断图中是否存在环、判断图的强连通分量等。
  • 组合问题：生成排列、组合或子集等组合型问题。
  • 寻路问题：求解从起始点到目标点的最短路径或所有可行路径。
  • 递归问题：通过递归实现深度优先搜索，例如二叉树的遍历等。

小华最多能得到多少克黄金

• 题目描述小华按照地图去寻宝，地图上被划分成 m 行和 n 列的方格，横纵坐标范围分别是 [0, n-1] 和 [0, m-1]。在横坐标和纵坐标的数位之和不大于 k 的方格中存在黄金（每个方格中仅存在一克黄金），但横坐标和纵坐标之和大于 k 的方格存在危险不可进入。小华从入口 (0,0) 进入，任何时候只能向左，右，上，下四个方向移动一格。请问小华最多能获得多少克黄金？输入要求坐标取值范围如下：k 的取值范围如下：输入中包含3个字数，分别是m, n, k输出要求输出小华最多能获得多少克黄金
  • 0 ≤ m ≤ 50
  • 0 ≤ n ≤ 50
• 0 ≤ k ≤ 100
• 例如，对于数字1234，它的各个位上的数字分别是1、2、3和4，那么它的数位之和就等于1+2+3+4=10。同样地，对于数字56789，它的数位之和就等于5+6+7+8+9=35。
• 在题目中，提到横纵坐标的数位之和不大于k，意味着将横坐标和纵坐标的每个位上的数字相加，得到的和要小于或等于k。
• 首先，可以定义一个函数 dfs 来进行深度优先搜索。这个函数可以接受当前位置的坐标 (x, y)、当前黄金数量 gold 和已经访问过的方格集合 visited 作为参数。
• 在 dfs 函数中，首先判断当前位置是否越界或者已经访问过，如果是则直接返回。然后判断当前位置的横纵坐标的数位之和是否大于 k，如果是则说明是危险方格，也直接返回。否则，将当前位置标记为已访问，并将当前位置的黄金数量加上当前方格的黄金数量。
• 接下来，递归地调用 dfs 函数来搜索当前位置的上、下、左、右四个方向的相邻方格。对于每个相邻方格，传入更新后的坐标和黄金数量，并将得到的结果取最大值。
• 最后，在主函数中，从入口位置 (0, 0) 开始调用 dfs 函数，并输出返回的最大黄金数量。

题解数位之和是指一个数的各个位上数字的和。这道题可以使用深度优先搜索（DFS）算法来解决。

importjava.util.*;publicclassMain{ staticint m, n, k;staticint[] xArr ={ -1,1,0,0}, yArr ={ 0,0,1,-1};publicstaticvoidmain(String[] args){ Scanner sc =newScanner(System.in);while(sc.hasNext()){  m = sc.nextInt(); n = sc.nextInt(); k = sc.nextInt();System.out.println(move(0,0,0,newHashSet<>()));

用例1

输入： 40 40 18 输出：1484 

用例2

输入： 5 4 7 输出：20