最大数字（java）(DFS实现)

1.最大数字 - 蓝桥云课

因为N最大是·10 的17次方，

所以可以利用字符串来处理输入的数字的每一位

并且是从高到低依次处理的

然后通过函数charAt(i)来获取第i位的字符

再减去‘0’就可以将字符转化为整型了

假设每一位数字都是x

然后通过两种操作

加或者减来操作

然后每次操作的话我们先判断加

如果这个数字的第i位还存在的话

那就可以进行加或者减

然后我们开始dfs之前先

判断加多少位，能把第一位变成9

我们尽最大的努力去把每一位都加到9

两种情况

第一种如果加法的次数最多不超过9-x 吧

因为加的次数多了又加到0了

做无用功了，你说对吧

第二种情况如果加法的次数不足以把x加到9

我们

加的次数就是9-x 和n 中的最小值

（9-x）也就是x加到9的次数

t 取（9-x）和 n 的最小值

回溯之前：剩余的加的次数就是n =n -t;

然后就开始dfs()嵌套循环了

开始的时候是

dfs(i,v) i表示当前这个数的位数的下标

v 用来保存操作之后的值

dfs(i+1,v*10+t) 表示进入下一位，便利下一个节点i+1

然后需要保存这一次加法之后的值

然后如果回溯回回来就需要把给加法次数加回来

ok自己写一遍

emm，又出问题了，孩子们

import java.util.Scanner;/*** @author zb* date2025/3/26 21:32*/
public class Main {static int n ;static int add;static   int jian;static String num;static int max = 0;public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();num = ""+n;add = in.nextInt();jian  = in.nextInt();
//       先从最高为开始操作dfs(0,0);System.out.println(max);in.close();}
//代表给第i位操作 ，v 用来保存操作的结果private static void dfs(int i, int v) {if(i<num.length()){
//            加法操作
//            获取第i位的数字int numi = num.charAt(i)-'0';
//            加到9所需要的次数int t = 9  - numi;
//            如果加的次数不能让这个数字加到9if(add<=t){
//              能加多少算多少t = add;}
//          减去消耗掉的加法次数add = add - t;
//            System.out.println(t+"   "+add);
//          便利叶子节点dfs(i+1,v*10 +numi+t);
//     从叶子节点变回来了     回复现场add = add+ t;
//            减法 的话一定要把这个数字给变成0
//           也就是减法必须要被这个位置的数字大
//            某一位最大只能变成9if(numi-jian<0&&numi!=9){
//                numi  = 9;
//               等于-1也就是变成9jian = jian - numi-1;
//                System.out.println("   "+jian);dfs(i+1,v*10 +9);jian  = jian + numi + 1;}}else {
//            保存进行操作之后得到的最大值max = Math.max(max,v);}}
}

整体思路没有问题，死于段错误

看了一下题目发现