（一）暴力递归
暴力递归就是尝试
1，把问题转化为规模缩小了的同类问题的子问题
2，有明确的不需要继续进行递归的条件（base case）
3，有当得到了子问题的结果之后的决策过程
4，不记录每一个子问题的解
一定要学会怎么去尝试，因为这是动态规划的基础，这一内容我们将在提升班讲述
1.汉诺塔问题
汉诺塔问题
打印n层汉诺塔从最左移动到最右边的全过程。
举例：三层汉诺塔问题，有左中右三个杆，1,2,3三个圆盘从大到小，从底到顶排列。
初始形态：1，左；2，左；3，左。第一步，1，左->右；第二步，2，左->中；第三步，1，右->中；第四步，3，左->右；第五步，1，中->左；第六步，2，中->右；第七步，1，左->右。
思路，对于1-i的圆盘，设定一个函数P(i,form,to,other),i表示当前圆盘，from表示出杆，to表示目前杆，other表示其它杆。
1）对于1~i-1的圆盘，将它从from移动到otther,调用的函数P(i~1,f,o,to)
2）对于i圆盘，将它从from移动到to,直接打印
3）对于1~i-1的圆盘，将它从other移动到to，调用的函数P(i~1,o,to,f)
现在以中间为最终位置，函数实现如下：
package Class008; public class Code_Hanoi { public static void hanoi(int n){ if(n>0){ func(n,"左","中","右"); } } //1-i圆盘目标是from->to,other是另外一个 public static void func(int i,String start,String end,String other){ if(i==1){ System.out.println("Move 1 from "+start+"to "+end); }else { func(i-1,start,other,end); System.out.println("Move "+i+" from "+start+"to "+end); func(i-1,other,end,start); } } public static void main(String [] args){ System.out.println("====3层汉诺塔===="); int n=3; hanoi(n); System.out.println("====5层汉诺塔===="); int n1=5; hanoi(n1); } }运行结果：
====3层汉诺塔==== Move 1 from 左to 中 Move 2 from 左to 右 Move 1 from 中to 右 Move 3 from 左to 中 Move 1 from 右to 左 Move 2 from 右to 中 Move 1 from 左to 中 ====5层汉诺塔==== Move 1 from 左to 中 Move 2 from 左to 右 Move 1 from 中to 右 Move 3 from 左to 中 Move 1 from 右to 左 Move 2 from 右to 中 Move 1 from 左to 中 Move 4 from 左to 右 Move 1 from 中to 右 Move 2 from 中to 左 Move 1 from 右to 左 Move 3 from 中to 右 Move 1 from 左to 中 Move 2 from 左to 右 Move 1 from 中to 右 Move 5 from 左to 中 Move 1 from 右to 左 Move 2 from 右to 中 Move 1 from 左to 中 Move 3 from 右to 左 Move 1 from 中to 右 Move 2 from 中to 左 Move 1 from 右to 左 Move 4 from 右to 中 Move 1 from 左to 中 Move 2 from 左to 右 Move 1 from 中to 右 Move 3 from 左to 中 Move 1 from 右to 左 Move 2 from 右to 中 Move 1 from 左to 中2.打印字符串的子序列
打印一个字符串的全部子序列，包括空字符串。
举例：“abc”的子序列，我们可以看成类似于对二叉树进行划分,形成一个以字符串长度为高的满二叉树，第i个字母有2^i条边，以供判断，最后根节点的yes标签统计的字符串，就是整个字符串的子序列。
n0 a(y) / \ a(n) / \ / \ n1 n2 b(y) / \ b(n) b(y) / \ b(n) / \ / \ / \ / \ n3 n4 n5 n6 c(y) / \ c(n) c(y) / \ c(n) c(y) / \ c(n) c(y) / \ c(n) / \ / \ / \ / \ / \ / \ / \ / \ abc ab ac a bc b c ''代码实现：
package Class008; import java.util.ArrayList; import java.util.List; public class Code_PrintAllSubsquences { //方法一，修改原字符数组 public static void printAllSubsquence(String str){ char[] chs=str.toCharArray(); process(chs,0); } //从左往右，每个字符要或不要做决策 //当前来到i位置，和要不要，走两条路 //之前的选择，形成的结果，是str public static void process(char[]chs, int i){ if(i==chs.length){ printChars(chs); return; } //要当前字符的路 process(chs,i+1); //把当前字符记为0字符，则走的是不要当前字符的路 char tmp=chs[i]; chs[i]=0; process(chs,i+1);//不要当前字符的路 chs[i]=tmp;//将str改回来 } public static void printChars(char[] chs) { StringBuilder builder = new StringBuilder(); for (char c : chs) { if (c != 0) {builder.append(c);} } System.out.println("\"" + builder + "\""); } //方法二，List保存之前的选择 public static void function(String str){ char[] chs=str.toCharArray(); process(chs,0,new ArrayList<Character>()); } //当前来到i位置，和要不要，走两条路 //List<Character>表示之前的选择形成的char类型的列表 public static void process (char[] str,int i,List<Character> res){ //i来到终止位置，打印之前的选择 if(i==str.length){ printList(res); return; } //把之前的选择拷贝一份，将当前的字符加进去，继续做过程 List<Character>resKeep=copyList(res); resKeep.add(str[i]); process(str,i+1,resKeep);//要当前字符的路 List<Character>resNoInclude=copyList(res); process(str,i+1,resNoInclude);//不要当前字符的路 } public static void printList(List<Character> res){ StringBuilder builder=new StringBuilder(); for (Character c : res){ builder.append(c); } System.out.println("\""+builder+ "\""); } public static List<Character>copyList(List<Character> list){ return new ArrayList<>(list); } public static void main(String[] args){ System.out.println("====方法一===="); String a="abc"; printAllSubsquence(a); System.out.println(); System.out.println("====方法二===="); String b="abc"; function(b); } }运行结果：
====方法一==== "abc" "ab" "ac" "a" "bc" "b" "c" "" ====方法二==== "abc" "ab" "ac" "a" "bc" "b" "c" ""| 方法 | 时间复杂度 | 额外空间复杂度 | 原因 |
|---|---|---|---|
方法一：修改char[]+ 恢复现场 | O(N × 2^N) | O(N) | 共2^N个结果，每次打印最多处理N个字符；递归深度为N |
方法二：不断copyList() | O(N × 2^N) | O(N²) | 每个递归节点需要复制已有 List；一条递归路径上会同时存在多个不同长度的 List |
3.打印一个字符串的全部排列
打印一个字符串的全部排列（leetcode47，剑指offer38）
打印一个字符串的全部排列，要求不要出现重复的排列
常见思路，固定第一个位置，排列剩下的N-1个位置；接着固定第二个位置，排列剩下的N-2个位置......以此类推。
示例代码：
package Class008; import java.util.ArrayList; public class Code_PrintAllPermutations { public static ArrayList<String>Permutation(String str){ ArrayList<String> res=new ArrayList<>(); if (str==null||str.length()==0){ return res; } char[] chs=str.toCharArray(); process(chs,0,res); res.sort(null); return res; } //str[i..]范围上，所有的字符，都可以在i位置上，后续都去尝试 //str[0..i-1]范围上，是之前做的选择 //请把所有字符串形成的全排列，加入到res里面去 public static void process(char[] chs,int i,ArrayList<String>res){ if(i==chs.length){ res.add(String.valueOf(chs)); } //给出26个小写字母表，对比进入排列的字母有没有试过 boolean[] visit=new boolean[26]; //这里的去重是用来降低常数项的时间复杂度的 //i位置的字母在试过之后才能注册上，下一次不再试，从而得到去重的全排列（比如abbc） for (int j=i;j<chs.length;j++){ if(!visit[chs[j]-'a']){ visit[chs[j]-'a']=true; //分支限界（剪枝），提前杀死不可能的路，比整个递归走完更快 swap(chs,i,j); process(chs,i+1,res); //第二个swap就是回溯。回溯=子递归调用完成后把环境恢复调用前状态 swap(chs,i,j); } } } public static void swap(char[] chs,int i,int j){ char tmp=chs[i]; chs[i]=chs[j]; chs[j]=tmp; } public static void main(String []args){ // ========================= // 测试1：无重复字符 // ========================= String str1 = "abc"; System.out.println("==== abc ===="); System.out.println(Permutation(str1)); // ========================= // 测试2：有重复字符 // ========================= String str2 = "abb"; System.out.println("==== abb ===="); System.out.println(Permutation(str2)); // ========================= // 测试3：多个重复字符 // ========================= String str3 = "abbc"; System.out.println("==== abbc ===="); System.out.println(Permutation(str3)); // ========================= // 测试4：全部字符相同 // ========================= String str4 = "aaa"; System.out.println("==== aaa ===="); System.out.println(Permutation(str4)); } }运行结果：
==== abc ==== [abc, acb, bac, bca, cab, cba] ==== abb ==== [abb, bab, bba] ==== abbc ==== [abbc, abcb, acbb, babc, bacb, bbac, bbca, bcab, bcba, cabb, cbab, cbba] ==== aaa ==== [aaa]4.抽数组纸牌问题
给定一个整型数组 arr，代表数值不同的纸牌排成一条线。玩家 A 和玩家 B 依次拿走每张纸牌，规定玩家 A 先拿，玩家 B 后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家 A 和玩家 B 都绝顶聪明。请返回最后获胜者的分数。(leetcode486，1423)
【举例】
arr = [1, 2, 100, 4]。
开始时，玩家 A 只能拿走 1 或 4。如果开始时玩家 A 拿走 1，则排列变为 [2, 100, 4]，接下来玩家 B 可以拿走 2 或 4，然后继续轮到玩家 A……
如果开始时玩家 A 拿走 4，则排列变为 [1, 2, 100]，接下来玩家 B 可以拿走 1 或 100，然后继续轮到玩家 A……
玩家 A 作为绝顶聪明的人不会先拿 4，因为拿 4 之后，玩家 B 将拿走 100。所以玩家 A 会先拿 1，让排列变为 [2, 100, 4]，接下来玩家 B 不管怎么选，100 都会被玩家 A 拿走。玩家 A 会获胜，分数为 101。所以返回 101。
arr = [1, 100, 2]。
开始时，玩家 A 不管拿 1 还是 2，玩家 B 作为绝顶聪明的人，都会把 100 拿走。玩家 B 会获胜，分数为 100。所以返回 100。
分析：
我们设先手情况下的函数为 int f(arr,L,R),只有一张牌的情况，if(L==R),return arr[L],当前获得的利益arr[L]增加,此时，边界范围变成(L+1,R)。于是建立一个函数arr[L]+s(arr,L+1,R),以计算后手选择左半边后自己已经获得的以及纸牌中最大的利益情况，arr[R]+s(arr,L,R-1)计算后手选择右半边后自己已经获得的以及纸牌中最大的利益情况。最终先手获得的最大利益计算函数为：max{arr[L]+s(arr,L+1,R),arr[R]+s(arr,L,R-1)}
接着我们计算后手最大利益计算函数。int s（arr，L，R）,当L==R时，return 0;由于先手和后手的利益是对立的，总和不变，那么就要保持先手决策函数变得最小，于是后手获得的最大利益计算函数为：
min{f(arr,L+1,R),f(arr,L,R-1)}
示例代码：
package Class008; public class Code_CardsInLine { public static int win1(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 i,int j){ if(i==j){ return arr[j]; } return Math.max(arr[i]+s(arr,i+1,j),arr[j]+s(arr,i,j-1)); } public static int s(int[]arr,int i,int j){ if(i==j){ return 0; } return Math.min(f(arr,i+1,j),f(arr,i,j-1)); } public static int win2(int[] arr){ if (arr==null|| arr.length==0){ return 0; } int[][]f=new int[arr.length][arr.length]; int[][]s=new int[arr.length][arr.length]; for(int j=0;j<arr.length;j++){ f[j][j]=arr[j]; for(int i=j-1;i>=0;i--){ f[i][j]=Math.max(arr[i]+s[i+1][j],arr[j]+s[i][j-1]); s[i][j]=Math.min(f[i+1][j],f[i][j-1]); } } return Math.max(f[0][arr.length-1],s[0][arr.length-1]); } public static void main(String []args){ int[]arr1={1,9,10}; System.out.println("列表：1,9,10"); System.out.println(win1(arr1)); System.out.println(win2(arr1)); // A是先手，B是后手 int A=f(arr1,0,arr1.length-1); int B=s(arr1,0,arr1.length-1); System.out.println("玩家A得分："+A); System.out.println("玩家B得分："+B); if(A>B){ System.out.println("玩家A获胜"); }else if(A<B){ System.out.println("玩家B获胜"); }else{ System.out.println("双方平局"); } int[]arr2={1,9,2,4,9,13,12}; System.out.println("列表：1,9,2,4,9,13,12"); System.out.println(win1(arr2)); System.out.println(win2(arr2)); // A是先手，B是后手 int A1=f(arr2,0,arr2.length-1); int B1=s(arr2,0,arr2.length-1); System.out.println("玩家A得分："+A1); System.out.println("玩家B得分："+B1); if(A1>B1){ System.out.println("玩家A获胜"); }else if(A1<B1){ System.out.println("玩家B获胜"); }else{ System.out.println("双方平局"); } int[]arr3={1,9,9,1}; System.out.println("列表：1,9,9,1"); System.out.println(win1(arr3)); System.out.println(win2(arr3)); // A是先手，B是后手 int A2=f(arr3,0,arr3.length-1); int B2=s(arr3,0,arr3.length-1); System.out.println("玩家A得分："+A2); System.out.println("玩家B得分："+B2); if(A2>B2){ System.out.println("玩家A获胜"); }else if(A2<B2){ System.out.println("玩家B获胜"); }else{ System.out.println("双方平局"); } } }运行结果：
列表：1,9,10 11 11 玩家A得分：11 玩家B得分：9 玩家A获胜 列表：1,9,2,4,9,13,12 26 26 玩家A得分：24 玩家B得分：26 玩家B获胜 列表：1,9,9,1 10 10 玩家A得分：10 玩家B得分：10 双方平局5.递归实现栈的逆序
给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现？
思路：
设置一个移除栈底元素的函数，返回值是移除的栈底的元素。
代码：
package Class008; import java.util.Stack; public class Code_ReverseStackUsingRecursive { public static void reverse(Stack<Integer>stack){ if (stack.isEmpty()){ return; } int i=f(stack); reverse(stack); stack.push(i); } public static int f(Stack<Integer>stack){ int result=stack.pop(); if(stack.isEmpty()){ return result; }else { int last=f(stack); stack.push(result); return last; } } public static void main(String[] args){ Stack<Integer>test=new Stack<Integer>(); test.push(1); test.push(2); test.push(3); test.push(4); test.push(5); reverse(test); while (!test.isEmpty()){ System.out.println("运行完成"); } } }分析：
f(stack) 函数流程：
作用：取出并返回栈底元素，同时保持其他元素顺序不变。
以栈 [1,2,3] 为例（1是栈底，3是栈顶）：
f1：弹出3，栈变成 [1,2]，继续调用f
f2：弹出2，栈变成 [1]，继续调用f
f3：弹出1，栈空，说明1是栈底元素，返回1
递归返回：
回到f2：push(2)，栈变成 [2]，返回1
回到f1：push(3)，栈变成 [2,3]，返回1
最终：返回值=1，栈=[2,3]
总结：f()负责取出栈底元素，并把其他元素按原顺序恢复。
reverse(stack) 函数流程：
作用：不断取出栈底元素，再利用递归返回顺序重新压栈，实现逆序。
原栈：[1,2,3]
递归进入：
reverse1：f取出1，剩下 [2,3]，继续reverse
reverse2：f取出2，剩下 [3]，继续reverse
reverse3：f取出3，剩下 []，继续reverse
reverse4：栈为空，return
递归返回：
回到reverse3：push(3)，栈=[3]
回到reverse2：push(2)，栈=[3,2]
回到reverse1：push(1)，栈=[3,2,1]
最终：
原栈：[1,2,3]
逆序后：[3,2,1]
一句话总结：
f：递归找到栈底元素并取出，其他元素恢复原样。
reverse：不断取栈底元素，栈空后再按递归返回顺序压回。
6.数字字符转化为字符串
规定1和A对应、2和B对应、3和C对应。
那么一个数字字符串比如"111"，就可以转化为"AAA"、"KA"和"AK"。
给定一个只含数字字符组成的字符串str，返回有多少种转化结果。（leetcode42，91）
分析：
这道题就是：
每个位置尝试“取1位”或者“取2位”，
只要取出的数字在1~26之间就可以继续，
最后统计一共有多少条合法路径。
来到 index 位置：
如果当前位置是0：
这条路无效，返回0
否则：
方法数 = 只取当前一位的方法数
如果当前位和下一位组成的数字 <= 26：
方法数 += 一次取两位的方法数
思路，可以将区间划分为两部分，一部分是已经确定的[0......i-1],另一部分是未确定的[i......]，我们要研究的是在确定前半部区间的条件下，后半部区间如何变化和调整。比如数字字符串“1110111”，我们设"0"位置对应的是i,如果设1=A，那么前半部“111”可以转为"AAA"(区间是[0,3]),然而后半部分"0111"是以"0"开头的，无法转换，没有意义，因此i=0时整个字符串没有意义。比如数字字符串“1113111”，我们设"3"位置对应的是i,如果设1=A，那么前半部“111”可以转为"AAA"(区间是[0,3]),然而后半部分"3111"是以"3"开头的，我们可以设"3"位置对应的是C,后面[5,8]位置上任意选择字母代替（比如BBB,AAA）。
如果对应的是1~9,我们把[1,9]整个区间分为（1~2）和（3~9）两部分，如果i为3~9之间的数字，那么只能做一个决定，那么也无法转化。
代码
package Class008; public class Code_ConvertToLetterString { public static int number(String str){ if (str==null||str.length()==0){ return 0; } return process(str.toCharArray(),0); } //i之前的位置，如何转化已经做过决定了 //i..有多少种转化的结果 public static int process(char[] chs,int i){ if (i==chs.length){ return 1; } if (chs[i]=='0'){ return 0; } if(chs[i]=='1'){ int res=process(chs,i+1);//i自己作为单独的部分，后续还有多少种方法 if(i+1<chs.length){ res+=process(chs,i+2);//i和i+1自己作为单独的部分，后续还有多少种方法 } return res; } if (chs[i]=='2'){ int res=process(chs,i+1);//i自己作为单独的部分，后续还有多少种方法 //确保后面有字符，且这个字符在0~6之间。 if (i+1<chs.length&&(chs[i+1]>='0'&&chs[i+1]<='6')){ res+=process(chs,i+2); } return res; } //str[i]=='3'-'9' return process(chs,i+1); } public static void main(String [] args){ System.out.println(number("1110111")); } }运行结果：
6
整个递归可以理解为：
当前位置是0： 无路可走，返回0 当前位置是1： 可以取1位 也可以取2位 当前位置是2： 可以取1位 如果下一位是0~6，还可以取2位 当前位置是3~9： 只能取1位 走到字符串末尾： 说明找到一种完整方案，返回1对于“1110111”，整个代码的流程如此：
process(0) ├─ 取1 -> process(1) │ ├─ 取1 -> process(2) │ │ ├─ 取1 -> process(3) = 0 │ │ └─ 取10 -> process(4) = 3 │ │ │ └─ 取11 -> process(3) = 0 │ └─ 取11 -> process(2) ├─ 取1 -> process(3) = 0 └─ 取10 -> process(4) = 3 最终： 3 + 3 = 6其中的六种切分依次对应：
1 | 1 | 10 | 1 | 1 | 1 1 | 1 | 10 | 1 | 11 1 | 1 | 10 | 11 | 1 11 | 10 | 1 | 1 | 1 11 | 10 | 1 | 11 11 | 10 | 11 | 1 AAJAAA AAJAK AAJKA KJAAA KJAK KJKA7.背包问题
给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少？
分析：这是0-1背包问题，从左往右依次遍历数组，判断要和不要，依次展开。
来到第i件物品：
不要它 -> 看 i+1 后面能得到多少价值
要它 -> 当前价值 + 看 i+1 后面能得到多少价值
答案 = 两种选择中较大的那个
第0件 / \ 不要 要 / \ 第1件 第1件 / \ / \ 不要 要 不要 要 ...代码：
package Class008; public class Code_Knapsack { public static int maxValue1(int[] weights,int[] values,int bag){ return process1(weights,values,0,0,bag); } //i... 的货物自由选择，形成的最大价值返回 //重量永远不要超过bag //之前做的决定，所达到的重量，alreadyweight public static int process1(int[] weights,int[] values, int i,int alreadyweight,int bag){ //所有物品已经考虑完 if (i==weights.length){ return 0; } //方案1：不要当前物品 int p1=process1(weights,values,i+1,alreadyweight,bag); //方案2：要当前物品 int p2=0; //只有不超重才要 if (alreadyweight+weights[i]<=bag){ p2=values[i]+process1(weights,values,i+1,alreadyweight+weights[i],bag); } return Math.max(p1,p2); // return Math.max( // process1(weights,values,i+1,alreadyweight,bag), // values[i]+process1(weights,values,i+1, // alreadyweight+weights[i],bag) // ); } //第二种写法,返回目前累计价值最终最大能到多少 public static int process2(int[] weights,int[] values, int i,int alreadyweight,int alreadyValue,int bag) { if (alreadyweight > bag) { return 0; } if (i == values.length) { return alreadyValue; } return Math.max(process2(weights, values, i + 1, alreadyweight, alreadyValue, bag), process2(weights, values, i + 1, alreadyweight+weights[i], alreadyValue + values[i], bag)); } //动态规划 //i = 当前来到第i件物品 // j = 之前已经使用了多少重量 //dp[i][j] = //在当前已经用了j重量的情况下， //从i号物品开始最多还能获得多少价值 public static int maxValue3(int[] c,int[]p,int bag){ int[][]dp=new int[c.length+1][bag+1]; for (int i=c.length-1;i>=0;i--){ for (int j=bag;j>=0;j--){ //不雅第i件 dp[i][j]=dp[i+1][j]; //如果第i件还能装进去，那么还可以考虑p[i] + dp[i + 1][j + c[i]] if (j+c[i]<=bag){ dp[i][j]=Math.max(dp[i][j],p[i]+dp[i+1][j+c[i]]); } } } return dp[0][0]; } // 第二种递归写法 public static int maxValue2(int[] weights, int[] values, int bag) { return process2(weights, values, 0, 0, 0, bag); } public static void main(String[] args) { int[] weights = {3, 2, 4, 7}; int[] values = {5, 6, 3, 19}; int bag = 11; System.out.println("递归方法1：" + maxValue1(weights, values, bag)); System.out.println("递归方法2：" + maxValue2(weights, values, bag)); System.out.println("动态规划：" + maxValue3(weights, values, bag)); } }运行结果：
递归方法1：25 递归方法2：25 动态规划：258.N皇后问题
N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上。
给定一个整数n，返回n皇后的摆法有多少种。
n=1，返回1。
n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0。
n=8，返回92。
思路：每一行只放一个棋子，第一行放完后，剩下行保证与之前行不共列不共斜线即可。
思路参考第七章。
代码：
package Class008; public class Code_NQueens { public static int num1(int n){ if (n<1){ return 0; } int[] record=new int[n];//record[i]->i行的皇后，放在了第几列 return process1(0,record,n); } public static int process1(int i,int [] record,int n){ if (i==n){ return 1; } int res=0; for (int j=0;j<n;j++){ //当前i行的皇后，放在j列，会不会和之前（0...n-1）的皇后，共行共列或共斜线， //如果是，认为无效 //如果不是，认为有效 if(isValid(record,i,j)){ record[i]=j; res+=process1(i+1,record,n); } } return res; } //record[0..i-1]你需要看，record[i...]不需要看 //返回i行皇后，放在了j列，是否有效 public static boolean isValid(int[] record,int i,int j){ for (int k=0;k<i;k++){//之前某个k行的皇后 if (j==record[k]||Math.abs(record[k]-j)==Math.abs(i-k)){ return false; } } return true; } public static int num2(int n){ if (n<1||n>32){ return 0; } int upperLim=n==32?-1:(1<<n)-1; return process2(upperLim,0,0,0); } //colLim列的限制，1的位置不能放皇后，0的位置可以 //leftDiaLim左斜线的限制，1的位置不能放皇后，0的位置可以 //rightDiaLim右斜线的限制，1的位置不能放皇后，0的位置可以 public static int process2(int upperLim,int colLim,int leftDiaLIm, int rightDiaLim){ if (colLim==upperLim){ return 1; } int pos=0; int mostRightOne=0; pos=upperLim&(~(colLim|leftDiaLIm|rightDiaLim)); int res=0; while (pos!=0){ mostRightOne=pos&(~pos+1); pos=pos-mostRightOne; res+=process2(upperLim,colLim|mostRightOne, (leftDiaLIm|mostRightOne)<<1, (rightDiaLim|mostRightOne)>>1); } return res; } public static void main(String [] args){ int n=14; //n皇后的优化对比 System.out.println("n=14时，n皇后的优化对比"); long start=System.currentTimeMillis(); System.out.println(num2(n)); long end=System.currentTimeMillis(); System.out.println("位运算优化后，cost time:"+(end-start)+"ms"); start=System.currentTimeMillis(); System.out.println(num1(n)); end=System.currentTimeMillis(); System.out.println("不优化时，cost time:"+(end-start)+"ms"); } }运行结果：
n=14时，n皇后的优化对比 365596 位运算优化后，cost time:144ms 365596 不优化时，cost time:2550ms
