目录
一.题目
二.代码
三.新知识点
一.题目
分析:给定一个整数，能在这个整数的任意数位插入加号构成一个表达式，求这个表达式的最大值和最小值，那就暴力搜索所有可能结果，求出最大值和最小值
二.代码
public class Main {//在动态规划和递归问题求极值时,对其进行极值初始化,确保没有比max小的,比min大的public static long max = Long.MIN_VALUE;public static long min = Long.MAX_VALUE;public static void main(String[] args) {Scanner scan = new Scanner(System.in);long n = scan.nextLong();int k = scan.nextInt();int[] arr = new int[19];//用于存储每一位数int index = 0;if(n==1){System.out.println(0);return;}while(n>0){arr[index++] = (int)(n % 10);n = n / 10;}//现在arr是逆序的n,将其转换为正序List<String> s = new ArrayList<>();for(int i = index-1;i>=0;i--){s.add(Integer.toString(arr[i]));}dfs(s,0,0,k,0,0);//从第一个元素开始System.out.println(max-min);scan.close();}public static void dfs(List<String> s,int index,int usedK,int k,long currentSum,long currentValue)//s是存储每一位数,尽量不要对s进行操作,会将问题变的复杂,我们应该进行动态的传参,将问题简单化//index代表的是当前下标,usedK是使用了几个k,currentSum是总和,currentValue是下一个加号前的值{//首先写结束语句if(index==s.size())//所有数字处理完毕{if(usedK==k)//数字和加号都处理完毕,因为会暴力所有结果,有可能一直没有插入加号或插入不够的情况,直接return{long total = currentSum + currentValue;max = Math.max(total,max);min = Math.min(total,min);}return;}//因为有两种情况:1.当前位置不插入加号 2.当前位置插入加号(实际是在当前数后面插入加号long currentNew = currentValue * 10 + Integer.valueOf(s.get(index));//将当前数加进去//情况1dfs(s,index+1,usedK,k,currentSum,currentNew);//因为当前位置没有插入,将本次数字加进去//情况2if(usedK!=k&&index!=s.size()-1)//k使用完了不进行插入,插入到最后一个数字不进行插入{dfs(s,index+1,usedK+1,k,currentSum+currentNew,0);//因为插入了加号所以要更新currentValue}}
}
三.新知识点
1.在dp和dfs求极值时，对初值进行极值化，让max最小，min最大，确保没有比min小的，没有比max大的
2.尽量不要进行插入删除操作，会引起并发和时间复杂度高的问题，将值进行动态传递，逻辑清晰，写起来简单简化了代码逻辑
3.为什么没有回溯usedK？
隐式的回溯了，这里只有一个usedK不需要进行显式回溯，参数传递就可以，因为每一个递归都可以看成一个单独的线程，是独立的，传入的是usedK+1没有实际的改变当前的usedK，只是参数传递
