锐客网

  1. 首页 > it技术 > >

动态规划|暴力递归经典问题

算法动态规划c++贪心算法回溯

一、前言 暴力递归延伸出了很多常见的算法：动态规划、贪心、回溯等。本篇文章将从它们的基本思想——递归入手，解决一些经典问题。

二、题目 1、汉诺塔问题
相信大家都玩过汉诺塔，简介如下：
动态规划|暴力递归经典问题
文章图片

初始给定三根柱子和一个从上到下依次增大的圆盘堆，初始时圆盘堆放在第一个柱子上，请你给出这些圆盘通过中间柱子为中介，最终达到最后一个柱子所需要的最优路径。（条件是一次只可以移动一个圆盘，并且小圆盘必须放在大圆盘上面。）
分析：这类的题目路径极为复杂，不方便直接看出。但是我们只要想出它的边界条件就可以推出总结果。首先，我们可以将初始柱子上的n-1个移动到中间那个柱子，然后将第n个圆盘移动到最终的柱子， 最后将中间的n-1个柱子移动回最终柱子即可。
是的，它只需要三步，假设我们已经有了一个函数fun（n，start，end），它的作用就是将n个圆盘从start移到end，那么这道题的步骤只有三步：

if n ==1
直接输出 move 1 from “start” to “end”
else
fun（n-1,"初始"，“中间”）//将n-1个移动到中间位置
打印 move n from “初始” to “最终”
fun（n-1,"中间"，“最终”）
这种递归就可以清晰的解决汉诺塔问题了
代码：

// 汉诺塔问题 public static void hanoi(int n){ if(n>0){ fun(n,"左","右","中"); } } public static void fun(int i,String start,String end,String other){ if(i==1) System.out.println("Move 1 from "+start+" to "+end); else{ fun(i-1,start,other,end); System.out.println("Move "+i+" from "+start+" to " +end); fun(i-1,other,end,start); } }


2、子序列、子集问题
这类题目分布很广泛，大概就是让你求一个字符串的所有子序列呀，或者一个集合的所有子集之类的。这种题目力扣上有很多，大多都是使用动态规划、贪心、滑动窗口等解决，但是其实他们的本质都是递归，找条件递归。
分析：如果我有一个字符串s，我如何求它的所有子序列呢？首先我将这样思考：
1、字符串不方便计算，我将它转化为char数组
2、我要求所有子序列，所以我新建一个List保存
3、一个长为n的字符串，每个字符我都有取和不取两种情况可以选择，所以一共2^n个子序列。
4、如果不使用List储存，那么我就要在每遍历完一次字符数组就要输出一次结果
5、为了方便4的输出，如果不取当前字符，就给它置0，完事后再变回来
我们通过process(chs,0)开始从头遍历字符数组（chs是字符数组），如果取当前字符，就直接process（chs，i+1）；如果不取，就先将chs[i]=0，然后再用process（chs，i+1），然后再将chs[i]恢复即可。这个递归的终止条件就是i==chs.length（这其实就类似回溯）。
代码：
// 打印一个字符串包括空字符串在内的所有子序列 public static void PrintSonStr(String s){ char[]chs=s.toCharArray(); process(chs,0,new ArrayList()); } public static void process(char[]chs, int i, List res){ if(chs.length==i) { for(char j:chs){ if(j!=0) System.out.print(j); } System.out.println(); return ; } process(chs,i+1,res); char tmp=chs[i]; chs[i]=0; process(chs,i+1,res); chs[i]=tmp; }


3、全排列问题
大家可能经常遇到一类问题，大多是求例如一个字符串的所有可能的排列顺序，其实解决方法还是大同小异。如果我们正在对第i个字符进行判断，那么前面的i-1个字符已经确定，只需要判断j从第i个数开始，到第n个数为止，i需不需要和第j个数交换，如果交换就递归调用，调用结束后再交换回来；还可以通过visit数组记录访问信息，防止重复发生。
代码：
// 全排列问题 public static ArrayList Quanpailie(String s){ ArrayListres=new ArrayList<>(); if(s==null||s.length()==0) return res; char []chs=s.toCharArray(); process2(chs,0,res); return res; } public static void process2(char[]str,int i,ArrayListres){ if(i==str.length) res.add(String.valueOf(str)); boolean[]visit=new boolean[26]; for(int j=i; j


4、聪明的人选纸牌问题
动态规划|暴力递归经典问题
文章图片

这道题目我们只需要写一个先手函数和一个后手函数就行，如果A在L到R上先取，它可能取左或者右，那么它在(L+1,R)或者(L,R-1)上就是后手取，并且取得两种取法的最大值。同理，如果B在L到R后手取，那么他在(L+1,R)或者(L,R-1)上就是先手取，并且返回两种取法最小值（因为最大值已经被A取走）。
代码：
// 绝顶聪明的人选纸牌问题 public static int XuanZhiPai(int[]arr){ if(arr==null||arr.length==0) return 0; return Math.max(f(arr,0,arr.length-1),s(arr,0,arr.length-1)); } public static int f(int[]arr,int l,int r){ if(l==r) return arr[l]; if(l<0||r>=arr.length||l>r) return 0; return Math.max(s(arr,l+1,r),s(arr,l,r-1)); } public static int s(int []arr,int l,int r){ if(l==r) return arr[l]; if(l<0||r>=arr.length||l>r) return 0; return Math.min(f(arr,l+1,r),f(arr,l,r-1)); }


5、栈的原地逆序
给定一个栈，需要你逆序这个栈，但是不可以使用额外的超过常数级别的空间。
代码：
public static void TurnStack(Stack stack){ if(stack.isEmpty()) return; int i = f1(stack); reverse(stack); stack.push(i); } public static int f1(Stack stack){ int ans = stack.pop(); if(stack.isEmpty()) return ans; else{ int last = f1(stack); stack.push(ans); return last; } } public static void reverse(Stackstack){ if(stack.isEmpty()) return; int i = f1(stack); reverse(stack); stack.push(i); }


6、
// 规定1和A对应，2和B对应... // 那么一个数字字符串比如“111”，就可以转化为“AAA”或者“KA”或者“AK” // 给定一个只有数字字符组成的字符串str，返回有多少种转化结果

代码：

public static int TurnToEn(String str){ if(str==null||str.length()==0) return 0; char[]chs=str.toCharArray(); returnprocess4(chs,0); } public static int process4(char[]str,int i){ if(i==str.length) return 1; if(str[i]=='0') return 0; if(str[i]=='1'){ int res = process4(str,i+1); if(i+1='0'&&str[i+1]<='6')) res+=process4(str,i+2); return res; } return process4(str,i+1); }


7、背包问题
// 给定两个长度都为N的数组weights和values，weights[i]和values[i] // 分别代表第i号物品的重量和价值，给一个正数bag，表示可以装bag的带子，求可以装的最大价值是多少

代码：
public static int MaxValue(int bag,int []weights,int []values){ return process5(bag,weights,values,0); } public static int process5(int bag,int[]weights,int[]values,int i){ if(bag<=0) return 0; if(i>=values.length) return0; return Math.max(process5(bag,weights,values,i+1),process5(bag-weights[i],weights,values,i+1)+values[i]); }


8、N皇后问题
代码：
public static int NQueen(int n){ if(n<1) return 0; int []record=new int[n]; return process7(n,record,0); } public static int process7(int n,int[]record,int i){ if(i==n) return 1; int res = 0; for(int j=0; j


三、尾言 代码半原创，有些部分我进行了删改，原创为马士兵教育。
【动态规划|暴力递归经典问题】最后几题没有解析实在是懒了。

    推荐阅读


    上一篇：学习笔记|uni-app开发小程序

    下一篇：喜欢的句子（二）