admin管理员组文章数量:1567278
暴力递归就是尝试
1:把问题转化为规模缩小了的同类问题的子问题
2:有明确的不需要继续进行递归的条件(base case)
3:有当得到子问题的结果之后的决策过程
4:返回每一个子问题的解给上级调用者
暴力递归–>动态规划
动态规划就是暴力尝试减少重复计算的技巧而已, 这种技巧就是一个大型套路,先写出用尝试的思路解决问题的递归函数,而不用操心时间复杂度 这个过程是无可替代的,没有套路的,只能依靠个人智慧,或者足够多的经验
但是怎么把尝试的版本,优化成动态规划,是有固定套路的,大体步骤如下
1)找到什么可变参数可以代表一个递归状态,也就是哪些参数一旦确定,返回值就确定了
2)把可变参数的所有组合映射成一张表,有 1 个可变参数就是一维表,2 个可变参数就 是二维表,…
3)最终答案要的是表中的哪个位置,在表中标出
4)根据递归过程的 base case,把这张表的最简单、不需要依赖其他位置的那些位置填好值
5)根据递归过程非base case的部分,也就是分析表中的普遍位置需要怎么计算得到,那 么这张表的填写顺序也就确定了
6)填好表,返回最终答案在表中位置的值
1.暴力递归
1.汉诺塔
public static void hannuo(int n){
if (n>0){
func(n,"左","右","中");
}
}
//1-i的圆盘(i越大,圆盘越大) 目标时from ->to other是另外一个柱子 !!每个子问题都保证自己的底满足规则即可
public static void func(int i,String start,String end,String other){
if (i == 1){
//base case 只剩下最小的盘 直接放就可以
System.out.println("移动 1 号盘,从"+start+"到"+end);
}else {
//先把i-1(大盘子i的上一个)放到辅助柱子上
func(i-1,start,other,end);
//第i-1的先搁置一边,这时候代表压在(i-1)下的大盘子i可以正确的放到目标柱子
System.out.println("移动"+i+" 号盘,从"+start+"到"+end);
//再把i-1从辅助柱子移到目标柱子。这时候满足规则,只能小压大
func(i - 1, other, end, start);
}
}
2.字符串的全部子序列
描述:比如给定abc 打印 abc ab,ac,a,bc ,b,c,null
思路:每个字符都选择要还是不要,和二叉树类似,再接着,每个子树又要选择要还是不要。就像下面这种,
开始选择要a或者不要a两种情况,然后根据前面的结果继续要b不要b两种情况,最终2^n种
public static void printAllSubsquence(String str){
char[] chs = str.toCharArray();
process(chs, 0,new ArrayList<Character>());
}
//来到i的位置,要还是不要两条路 ,res储存的是之前的选择所形成的的列表
private static void process(char[] chs, int i, List<Character> res) {
//base case 只要来到了终止的位置,即遍历完所有的字符串的时候,打印出来结果即可
if (i ==chs.length){
printList(res);//自己的处理逻辑 我这里是打印 也可以自己收集起来然后遍历所有结果打印
return;
}
//把之前的结果拷贝一份,让我们的下一个栈操作这个拷贝的就行,原来的后面还要用,所以需要拷贝。
List<Character> resKeep = copyList(res);
resKeep.add(chs[i]); //加入当前字符
//继续走要当前字符的路 比如为空 加入后变为'a',那我们就要'a'的路
process(chs,i+1,resKeep);
//拷贝一份,因为我们没有添加当前字符,而是直接走的i+1下一个字符的这条路
List<Character> resNoinclude = copyList(res);
process(chs,i+1,resNoinclude);//不要当前的路
}
//工具函数,将之前存放的结果的list再复制一份放到一个新的list里
private static List<Character> copyList(List<Character> oldList) {
if (oldList == null){
return new ArrayList<Character>();
}
ArrayList<Character> newList = new ArrayList<>();
for (Character ch : oldList) {
newList.add(ch);
}
return newList;
}
//工具函数,打印list里所有的字符串
private static void printList(List<Character> res) {
for (Character ch : res) {
System.out.print(ch);
}
System.out.println();
}
3.字符串全排列且去重
字符串全排列力扣地址
描述:如输入字符串abc,则字符a、b、c 所能排列出来的所有字符串:abc、acb、bac、bca、cab 和 cba
思想:就是去试,str[0…i-1]范围上,是之前做的选择,是已经试好的(可以看做固定的),str[i…]范围上,所有的字符都可以在i位置上,后续都去尝试
public static ArrayList<String> CharQuanpailie(String str) {
if (str == null || str.length() == 0) return res;
ArrayList<String> res = new ArrayList<>();
char[] chs = str.toCharArray();
process(chs, 0, res); //从i=0开始
return res;
}
//把所有字符串形成的全排列加到res后返回
public static void process(char[] str, int i, ArrayList<String> res) {
//base case i作为指针走到末尾加入结果
if (i == str.length){
//这个str是被复用的,是递归栈保证了它每次先入栈,在方法调用的时候再从栈里取出而不销毁
res.add(String.valueOf(str));
//所以i == str.length时其实是最后一个str被加到res里
}
//为了不重复,分支限界,设置标志位,比如字符串中有两个a,则后面再次遇到a就不用再来一遍了
boolean[] visit = new boolean[26];
//从i位置开始,其余的所有字符都要试一遍组合,直到字符用完
for (int j = i; j < str.length; j++) {
//26个字母,减去'a'后变为 a对应0位置,b对应1位置....,哪个位置被用了,这个位置就置true
//如果该字符没被用,就可以通过该字符来全排列,这样就保证了不重复的字母才被考虑
if (!visit[str[j]-'a']){
//如果之前没用,现在用了,该位置置true
visit[str[j] - 'a'] = true;
//i往后所有的字符都可以来到i位置,比如开始'abc'则a后面的b、c字符也可以来到当前a位置
swap(str, i, j);
process(str,i+1,res);//j来到位置i后,从i+1开始尝试
//尝试完再放回去,把交换完的复原,依次往复
swap(str, i, j);
}
}
}
//工具类,交换位置
private static void swap(char[] str, int i, int j) {
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
4.逆序实现栈
描述:给你一个栈,请你逆序这个栈,不能申请额外的数据结构,只能使用递归函数。如何实现?
思路:
getAndRemoveLastElement方法递归之后:每次把当前值压回去
public class reverseStack {
public static void reverseStack(Stack<Integer>stack){
if (stack.isEmpty()) return;
int i = getAndRemoveLastElement(stack);
//弹出一个数之后,现在栈只有1,2了 然后继续逆序找到最后一个数字
reverseStack(stack);
stack.push(i);
}
//移除栈底元素并返回,剩下的盖下来
public static int getAndRemoveLastElement(Stack<Integer> stack){
Integer result = stack.pop();
//如果弹出一个数栈为空了,说明这个数就是最后一个了,直接返回
if (stack.isEmpty()) return result;
else {
int last = getAndRemoveLastElement(stack);//获得返回的
stack.push(result);//然后将当前的值重新入栈
return last;//返回上个栈返回的元素
}
}
}
5.取扑克
力扣地址
public static int win(int[] arr) {
if (arr == null || arr.length == 0) return 0;
//玩家1在【0,n-1】范围上先手, 玩家2在【0,n-1】范围上后手
//谁得分大谁赢
return Math.max(first(arr, 0, arr.length - 1), second(arr, 0, arr.length - 1));
}
//先手 在【i.j】范围上返回经过先手能得到的最大分数
public static int first(int[] arr,int i,int j){
if (i==j) return arr[i]; //先手,剩一张牌,就只能拿这张牌了
//由于只能取两边,取i后,剩下的为【i+1,j】范围,第二次取数(第二次可以看做后手);或者取j后,剩下的为【i,j-1】范围,第二次取数
//如何对先手的人有利,那就是取最大
return Math.max(arr[i]+second(arr,i+1,j),arr[j]+second(arr,i,j-1));
}
//后手 返回经过后手后,在【i.j】范围上能得到的最大分数
private static int second(int[] arr, int i, int j) {
if (i==j) //base case 后手,只有一个数,那会被先手拿走,所以只能得到0
return 0;
//如果别人先拿走i,我只能在【i+1,j】范围上轮到我先手
// 如果别人先拿走j,我只能在【i,j-1】范围上轮到我先手
//如何对后手的人有利,这里逆向思维,后手只有通过先手的结果确定,所以是动态的,两人敌对又聪明,分数越高越好。那么,作为后手的最大分数是被人决定的(先手的那个人),别人只会把最差情况给我,所以我要把最差情况最小化
return Math.min(first(arr, i + 1, j), first(arr, i, j - 1));
}
6.岛屿问题
力扣岛屿问题
思想:当当前位置为1的时候,就开始递归感染他附近的位置,并置为2,然后递归的时候就会计算有多少岛屿
public int numIslands(char[][] grid) {
//如果数组为null 或者第一行为null
if(grid == null || grid[0]==null) return 0;
int row=grid.length;
int res=0;
for(int i=0;i<grid.length;i++)
for(int j=0;j<grid[0].length;j++){
//如果当前位置为 1 则代表有岛
if(grid[i][j]=='1'){
res++;
//数量增加之后,把它相邻的1全部感染了
infect(grid,i,j,grid.length,grid[0].length);
}
}
return res;
}
//感染逻辑
public void infect(char[][] grid,int i,int j,int line,int row){
//当行大于了最大行数,或者行小于0,或者列同样如此,或者当前数不为1,直接跳出返回
if(i>=line || i<0 || j>=row || j<0 || grid[i][j]!='1') return ;//终止条件
//否则 说明当前位置为1,就需要把当前位置感染为不为1的其他数,这里我设置的为2,反正不为1就行了
grid[i][j]='2';
//然后递归的感染前后左右
infect(grid,i+1,j,line,row);//前 俯视图
infect(grid,i-1,j,line,row);//后
infect(grid,i,j+1,line,row);//右
infect(grid,i,j-1,line,row);//左
}
2.解码方法
1.数字转字符串
数字转字符串力扣地址:跟19题类似 约束版 爬楼梯 只是这道题由于0可以对应a 则 方案一始终都是可行的
public static int translateNum(int num) {
String str = String.valueOf(num);
int[] dp=new int[str.length()+1];
dp[0]=1;
for (int i = 1; i <= str.length(); i++) {
dp[i]=dp[i-1];
//当前字符不是字符串第一个字符 && (前一个字符为1 || 前一个字符为2&&当前字符小于7) 则可以从i-2的位置到达到当前位置 可以理解为i和i-1看成一个整体cur i-2就可以来到当前整体
if(i>1 && (str.charAt(i-2)=='1' || (str.charAt(i-2)=='2'&&str.charAt(i-1)<='5')))
dp[i]+=dp[i-2];
}
return dp[str.length()];
}
2.解码方法
力扣地址
/*相当于约束版本的爬楼梯 dp[i]=dp[i-1]+dp[i-2] dp[i]代表来到当前情况有多少种
来到当前字符cur 有2中情况:
1:只由当前字符解码 需要判断当前字符是不是0 dp[i-1]
2:由当前字符和前一个字符相加来解码 需要判断是否超过了26 dp[i-2]
然后方案一的情况+方案二的情况就是当前的cur的情况
*/
public int numDecodings(String s) {
if(s.charAt(0)=='0') return 0;
int[] dp=new int[s.length()+1];
dp[0]=1;//当有0个数则为空串 则有1种
for (int i = 1; i <=s.length() ; i++) {
// 由于我是从1开始算的 所以s.charAt(i-1)表示当前字符
//如果当前字符为0,则方案一的情况为0
if(s.charAt(i-1)=='0') dp[i]=0;
//否则就是dp[i]=dp[i-1]
else dp[i]=dp[i-1];
//当前字符不是首字母 && (前一个字符为1 || 前一个字符为2&&当前字符小于7) 则可以从i-2的位置到达到当前位置 相当于走2步嘛
if(i>1 && (s.charAt(i-2)=='1' || (s.charAt(i-2)=='2'&&s.charAt(i-1)<'7')))
dp[i]+=dp[i-2];
}
return dp[s.length()];
}
3.背包问题
背包问题
/*dp[i][j]表示:对于前i个物品,当前背包的容量为j时,这种情况下可以装下的最大价值是dp[i][j]。分两种情况
1.没有把这第i个物品装入背包,那么最大价值dp[i][j]=dp[i-1][j]。你不装嘛,那就继承之前的结果。
2.把这第i个物品装入了背包,那么dp[i][j]=dp[i-1][v-vw[i][0]]+vw[i][1]。
但还是需要和不装入进行大小比较,取价值最大的。
*/
public int knapsack (int V, int n, int[][] vw) {
//dp[i][j]代表来到当前位置j和使用了vw[0..i]的最大最大重量
int[][] dp=new int[n][V+1];
//当背包V=0 则初始化第0列全为0
for(int i=0;i<n;i++)
dp[i][0]=0;
//初始化第0行 这里我没有像上图多定义了一行(0个物品) 下面我直接从第一个物品开始的
for(int i=0;i<V+1;i++)
dp[0][i]=i>=vw[0][0]?vw[0][1]:0;
for(int i=1;i<n;i++){
for(int v=1;v<V+1;v++){
/*当前位置可以选择装还是不装
1.当前位置不装 则当前位置直接是他上面那个状态 dp[i][v]=dp[i-1][v];
2.当前位置装 则v-vw[i][0]代表需要装当前位置的时候 前面最大只能有v-vw[i][0]的体积,则 取dp[i-1][v-vw[i][0]]的位置为前面最大能够装的体积的重量最大值,然后加上当前位置的重量 最后然后1和2取最大值;
如果前面的v-vw[i][0]体积>=0,说明要了当前位置 前面的位置也能到达,则取方案1和2中的较大值。如果v-vw[i][0]体积<0,则说明要了当前位置之后,前面的又不满足了,这个时候当前位置只能选择方案1*/
if(v-vw[i][0]>=0)
dp[i][v]=Math.max(dp[i-1][v],dp[i-1][v-vw[i][0]]+vw[i][1]);
else dp[i][v]=dp[i-1][v];
}
}
return dp[n-1][V];
}
背包问题2:背包容量为w。一共有n袋零食, 第i袋零食体积为v[i]。在总体积不超过背包容量的情况下,一共有多少种零食放法(总体积为0也算一种放法)
public static int ways(int[] arr, int w) {
if (arr == null || arr.length == 0 || w < 0) return 0;
//dp[i][j]代表当前位置使用了arr[0..i]个物体(不一定每个数都要)放到j体积的方法数
int[][] dp = new int[arr.length][w + 1];
//初始化第0列,因为体积为0也算一种 所以当总体积j=0 也算一种
for (int i = 0; i < arr.length; i++)
dp[i][0] = 1;
//初始化第0行 看看当前j是否大于v[0] 如果大于等于则放得下 否则放不下
for (int j = 1; j <= w; j++)
dp[0][j] = j >= arr[0] ? 2 : 1;
/*来到当前位置dp[i][j]有2种情况
1.不要当前位置的i 直接是当前位置上面那个i-1位置得来 dp[i][j] = dp[i - 1][j];
2.要当前位置i 则到上面那个i-1位置需要的容量最大就是j-arr[i] 当然前提条件就是能够到达j-arr[i]体积大小
也就是j-arr[i]>=0 则dp[i][j] = dp[i - 1][j - arr[i]];
然后1+2就是当前位置的总方法数 */
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j <= w; j++) {
dp[i][j] = dp[i - 1][j];
if (j - arr[i] >= 0) {
dp[i][j] += dp[i - 1][j - arr[i]];
}
}
}
return dp[arr.length - 1][w];
}
4.停在原地的方法数
力扣地址
public int numWays(int steps, int arrLen) {
if(arrLen==1) return 1;
//如果不这么写的话 会超出内存 当步数不大但是数组长度很长时,数组靠后大部分位置没有必要去遍历
//因为步长为steps,而你要到达0 所以是一个来回 理论上指针可以到达的极限位置也就是steps/2+1,因此可以修改取值范围、
int maxCol = Math.min(steps/2+1,arrLen-1);
//dp[i][j]代表 使用了i步之后 来到j位置 的方法数
int[][] dp = new int[steps+1][maxCol+1];
//初始化行 开始的时候步数为为0 只有dp[0][0]=1 其他都为0
dp[0][0]=1 ;
for (int i = 1; i <steps+1 ;<
版权声明:本文标题:暴力递归&动态规划 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1726763914a1083384.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论