暴力遞歸就是嘗試
- 把問題轉(zhuǎn)化為規(guī)谋⒅簦縮小了的同類問題的子問題
- 有明確的不需要繼續(xù)進行遞歸的條件（base case)
- 有當(dāng)?shù)玫搅俗訂栴}的結(jié)果之后的決策過程
- 不記錄每一個子問題的解
漢諾塔問題
有三個可以使用的桿，將從大到小擺放的圓盤移到另一個桿子上给僵。圓盤在的桿子為from，圓盤要去的桿子為to详拙，剩下的桿子叫other
- 把i-1從from移到other
- 把i從from移到end
- 把i-1從other移到end
打印一個字符串的全部子序列（子集）帝际，包括空字符串
解決方法：
- 遍歷所有的字符，每個字符都有兩種處理方式饶辙，要或者不要
- 處理要和不要兩種狀態(tài)蹲诀，如果要，將字符加到要輸出的list中弃揽，如果不要脯爪，就不加字符
- 遍歷到最后一個字符则北，將其輸出
打印一個字符串的全部排列，要求不要出現(xiàn)重復(fù)的排列.
- 全排列是指痕慢，相同的字符尚揣，將字符放在不同順序的排列。
- 每個位置嘗試放字符串里的所有字符守屉。
給定一個整型數(shù)組arr惑艇，代表數(shù)值不同的紙牌排成一條線。
玩家A和玩家B依次拿走每張紙牌滨巴，規(guī)定玩家A先拿，玩家B后拿俺叭，但是每個玩家每次只能拿走最左或最右的紙牌，玩家A和玩家B都絕頂聰明熄守。請返回最后獲勝者的分?jǐn)?shù)。
【舉例】
arr=[1,2,100,4]裕照。
開始時攒发，玩家A只能拿走1或4晋南。如果開始時玩家A拿走1，則排列變?yōu)閇2,100,4]负间，接下來玩家 B可以拿走2或4，然后繼續(xù)輪到玩家A...
如果開始時玩家A拿走4政溃，則排列變?yōu)閇1,2,100]趾访，接下來玩家B可以拿走1或100董虱，然后繼
續(xù)輪到玩家A...
玩家A作為絕頂聰明的人不會先拿4，因為拿4之后愤诱，玩家B將拿走100。所以玩家A會先拿1转锈，
讓排列變?yōu)閇2,100,4]，接下來玩家B不管怎么選楚殿，100都會被玩家 A拿走撮慨。玩家A會獲勝竿痰，
分?jǐn)?shù)為101。所以返回101砌溺。
arr=[1,100,2]影涉。
開始時，玩家A不管拿1還是2规伐，玩家B作為絕頂聰明的人蟹倾，都會把100拿走。玩家B會獲勝猖闪，
分?jǐn)?shù)為100鲜棠。所以返回100。
- 模擬天才腦子里的計算思路培慌，用笨方法去試
- 對于同一個整型數(shù)組豁陆，
- 先手函數(shù)，計算拿走左邊紙牌加后手剩下紙牌得到的分?jǐn)?shù)與拿走右邊紙牌加后手剩下紙牌得到的分?jǐn)?shù)吵护，選擇分?jǐn)?shù)較高的一邊
- 后手函數(shù)盒音，去掉左邊紙牌后先手剩下的紙牌得到的分?jǐn)?shù)與去掉右邊紙牌后先手剩下的紙牌得到的分?jǐn)?shù)，選擇較低分?jǐn)?shù)的方案馅而。因為對方會選擇對我最不利的方法祥诽。
- 先手和后手函數(shù)的區(qū)別，如果整型數(shù)組里只有一個數(shù)瓮恭，先手可以得到它雄坪，后手不能得到它
給你一個棧，逆序這個棧偎血，不能申請額外的數(shù)據(jù)結(jié)構(gòu)诸衔，只能使用遞歸函數(shù)，如何實現(xiàn)颇玷？
- 遞歸1,每次遞歸存棧底的值笨农，棧pop到空后，依次返回帖渠，并將值push
- 遞歸2,目的是取到棧底的值谒亦，每次取出棧頂?shù)闹担绻麠榭湛战迹祷胤菡校绻麠２粸榭眨阎抵匦聀ush入棧
規(guī)定1和A對應(yīng)狞甚、2和B對應(yīng)锁摔、3和C對應(yīng)
那么一個數(shù)字字符串{”111“）可以轉(zhuǎn)化為字符字符串（”AAA“）、”KA“哼审、”AK“谐腰，
給定一個只有數(shù)字字符串組成的字符串str孕豹，返回有多少種轉(zhuǎn)化結(jié)果。
- 假設(shè)0 - i - 1 位置的轉(zhuǎn)化已經(jīng)決定好了十气，只考慮i之后的轉(zhuǎn)化
- 如果i位置為0,則無法轉(zhuǎn)換
- 如果i位置非0, 情況一励背，i位置轉(zhuǎn)化為對應(yīng)字符，或者i位置和i+1位置不能組成字符砸西，繼續(xù)遞歸處理i+1位置叶眉；情況二衅疙，i位置和i+1位置可以組成字符杖狼，將其轉(zhuǎn)換為字符，繼續(xù)遞歸處理i+2位置
給定兩個長度都為N的數(shù)組weights和values蝶涩，weights[i]和values[i]分別代表i號物品的重量和價值。給定一個正數(shù)bag嗽上，表示一個載重bag的袋子熄攘，你裝的物品不能超過這個重量。返回你能裝下最多的價值是多少浅萧？
思路：
- 每個位置要或者不要哲思，找出符合條件（重量不能超過袋子）的最多的價值
- 每次遞歸處理i位置的值，每次遞歸有兩種選擇棚赔，要i位置或者不要i位置，選擇能獲得最大價值的選擇丧肴。
- basecase, 當(dāng)現(xiàn)有重量超過袋子的重量胧后，該選擇不能要，返回0,當(dāng)現(xiàn)在的位置超過了N壳快，返回現(xiàn)有重量江醇。
N皇后問題
是指在N*N的棋盤上要擺N個皇后，要求任何兩個皇后不同行凛驮、不同列， 也不在同一條斜線上宏胯。 給定一個整數(shù)n，返回n皇后的擺法有多少種肩袍。 n=1婚惫，返回1。 n=2或3艰管，2皇后和3皇后問題無論怎么擺都不行蒋川，返回0。 n=8捺球，返回92。
- 復(fù)雜度較高o（nn）
public class NQueens {
public static int num1(int n){
if(n < 1){
return 0;
}
int[] record = new int[n];//表示index行裂逐，int[index]列放了皇后
return process(0, record, n);
}
//record[0..i-1]的皇后一定不共行胆剧，不共列，不共斜線
//目前來到了第i行
//record[0..i-1]表示之前的行篙悯，放了皇后位置
//n表示整體一共有多少行
//返回值是铃绒，擺完所有的皇后，合法的擺法有多少種
public static int process(int i, int[] record, int n){
if( i == n){ // 終止行
return 1;
}
int res = 0;
for(int j = 0; j < n; j++){
if(isValid(record, i, j)){
record[i] = j;
res += process(i + 1, record, n);
}
}
return res;
}
public static boolean isValid(int[] record, int i, int j){
for(int k = 0; k < i; k++){
if(j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)){
return false;
}
}
return true;
}
}
