演算法初級面試題08——遞迴和動態規劃的精髓、階乘、漢諾塔、子序列和全排列、母牛問題、逆序棧、最小的路徑...

動態規劃揹包問題 · 發表 2019-02-06 23:49:00

摘要：第八課主要介紹遞迴和動態規劃介紹遞迴和動態規劃暴力遞迴： 1，把問題轉化為規模縮小了的同類問題的子問題 2，有明確的不需要繼續進行遞迴的條件(base case) 3，有當得到了子問題的結果之後的決策過程 4，不記錄每一個子問題的解動態規劃 1，從暴...

第八課主要介紹遞迴和動態規劃

介紹遞迴和動態規劃

暴力遞迴：

1，把問題轉化為規模縮小了的同類問題的子問題

2，有明確的不需要繼續進行遞迴的條件(base case)

3，有當得到了子問題的結果之後的決策過程

4，不記錄每一個子問題的解

動態規劃

1，從暴力遞迴中來

2，將每一個子問題的解記錄下來，避免重複計算

3，把暴力遞迴的過程，抽象成了狀態表達

4，並且存在化簡狀態表達，使其更加簡潔的可能

圖靈引入的是：我不知道怎麼算，但是我知道怎麼試。知道怎麼暴力破解出來。

要學會，練習懂得怎麼嘗試。

題目一

求n!的結果

迴圈是一個知道怎麼算的過程（從1乘到n）。

遞迴是子問題拆分到最小問題的嘗試過程。

public class Code_01_Factorial {
public static long getFactorial1(int n) {
if (n == 1) {
return 1L;
}
return (long) n * getFactorial1(n - 1);
}

public static long getFactorial2(int n) {
long result = 1L;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}

public static void main(String[] args) {
int n = 5;
System.out.println(getFactorial1(n));
System.out.println(getFactorial2(n));
}

}

題目二

漢諾塔問題（不能大壓小，只能小壓大）

列印n層漢諾塔從最左邊移動到最右邊的全部過程

左中右另稱為 from、to、help。

劃分子問題

1、先把1~n-1從from移動到help

2、把單獨的n移動到to

3、1~n-1從help移動到to

時間複雜度就是：

T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1)+1（一個等比公式）

T(n-1)是移動到help

1是從from直接移動到to

T(n-1)是把全部n-1挪回去

總的步數是2的N次方減一

這個題目要學會嘗試。

也可以寫六個移動的遞迴，來逐一實現步驟。

（該問題最基礎的一個模型就是，一個竹竿上放了2個圓盤，需要先將最上面的那個移到輔助竹竿上，然後將最底下的圓盤移到目標竹竿，最後把輔助竹竿上的圓盤移回目標竹竿。）

public class Code_02_Hanoi {

public static void hanoi(int n) {
if (n > 0) {
func(n, n, "left", "mid", "right");
}
}

public static void func(int rest, int down, String from, String help, String to) {
if (rest == 1) {
System.out.println("move " + down + " from " + from + " to " + to);
} else {
func(rest - 1, down - 1, from, to, help);
func(1, down, from, help, to);
func(rest - 1, down - 1, help, from, to);
}
}

//課堂上的程式碼
//N 表示當前是 1~N的問題
//一開始都在from上
public static void process(int N, String from, String to, String help) {
if (N == 1) {//就只有一個了，可以直接移動
System.out.println("Move 1 from " + from + " to " + to);
} else {//否則就是1~N的問題
process(N - 1, from, help, to);//把1~N-1個從from移動到help
System.out.println("Move " + N + " from " + from + " to " + to);//單獨把N移動到to
process(N - 1, help, to, from);//第三步是挪回來,把在help上的挪到to
}
}

public static void moveLeftToRight(int N) {
if (N == 1) {
System.out.println("move 1 from left to right");
} else {
moveLeftToMid(N - 1);//先把N-1移動到中間
System.out.println("move " + N + "from left to right");//把N移動到目的地
moveMidToRight(N - 1);//再把N-1移動到目的地
}
}

public static void moveRightToLeft(int N) {

}

public static void moveLeftToMid(int N) {
if (N == 1) {
System.out.println("move 1 from left to mid");
}
moveLeftToRight(N - 1);
System.out.println("move " + N + "from left to mid");
moveRightToMid(N - 1);
}

public static void moveMidToLeft(int N) {

}

public static void moveRightToMid(int N) {

}

public static void moveMidToRight(int N) {
if (N == 1) {
System.out.println("move 1 from mid to right");
}
moveMidToLeft(N - 1);
System.out.println("move " + N + "from mid to right");
moveLeftToRight(N - 1);
}

public static void main(String[] args) {
int n = 3;
hanoi(n);
}

}

題目三

列印一個字串的全部子序列，包括空字串

怎麼把腦裡面的嘗試變成code，就是寫遞迴的能力

嘗試方法：

一開始是空字串，經過0有兩個決定要a和不要a，經過1也要決定要不要b，一直嘗試下去，列舉所有情況。

可以畫一下你想嘗試的圖，先來個小規模的，再去寫遞迴就沒那麼難寫了。

public class Code_03_Print_All_Subsquences {

public static void printAllSubsquence(String str) {
char[] chs = str.toCharArray();
process(chs, 0);
}

public static void process(char[] chs, int i) {
if (i == chs.length) {
System.out.println(String.valueOf(chs));
return;
}
process(chs, i + 1);
char tmp = chs[i];
chs[i] = 0;//用空格代替字元
process(chs, i + 1);
chs[i] = tmp;//直接使用字元
}

//public static void function(String str) {
//char[] chs = str.toCharArray();
//process(chs, 0, new ArrayList<Character>());
//}
//
//public static void process(char[] chs, int i, List<Character> res) {
//if(i == chs.length) {
//printList(res);
//}
//List<Character> resKeep = copyList(res);
//resKeep.add(chs[i]);
//process(chs, i+1, resKeep);
//List<Character> resNoInclude = copyList(res);
//process(chs, i+1, resNoInclude);
//}
//
//public static void printList(List<Character> res) {
//// ...;
//}
//
//public static List<Character> copyList(List<Character> list){
//return null;
//}

//課堂上的版本
public static void printAllSub(char[] str,int i,String res){
if (i == str.length){//到達字串的末尾，已經沒有選擇了
System.out.println(res);
return;
}
printAllSub(str,i+1,res+" ");//不要當前字元的路
printAllSub(str,i+1,res+str[i]);//要當前字元的路
}

public static void printAllPermutation(){

}

public static void main(String[] args) {
String test = "abc";
printAllSubsquence(test);
printAllSub(test.toCharArray(),0,"");
}

}

題目四

列印一個字串的全部排列

進階

列印一個字串的全部排列，要求不要出現重複的排列

public class Code_04_Print_All_Permutations {

public static void printAllPermutations1(String str) {
char[] chs = str.toCharArray();
process1(chs, 0);
}

public static void process1(char[] chs, int i) {
if (i == chs.length) {
System.out.println(String.valueOf(chs));
}
for (int j = i; j < chs.length; j++) {
swap(chs, i, j);
process1(chs, i + 1);
swap(chs, i, j);//回溯
}
}

public static void printAllPermutations2(String str) {
char[] chs = str.toCharArray();
process2(chs, 0);
}

public static void process2(char[] chs, int i) {
if (i == chs.length) {
System.out.println(String.valueOf(chs));
}
HashSet<Character> set = new HashSet<>();
for (int j = i; j < chs.length; j++) {
if (!set.contains(chs[j])) {
set.add(chs[j]);
swap(chs, i, j);
process2(chs, i + 1);
//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) {
String test1 = "abc";
printAllPermutations1(test1);
System.out.println("======");
printAllPermutations2(test1);
System.out.println("======");

String test2 = "acc";
printAllPermutations1(test2);
System.out.println("======");
printAllPermutations2(test2);
System.out.println("======");
}

}

題目五

母牛每年生一隻母牛，新出生的母牛成長三年後也能每年生一隻母牛，假設不會死。求N年後，母牛的數量。

一遇到這種遞推的題目，不知道怎麼試，先列出前幾項，遞推是有高度結構化的解的。

然後要想為什麼？

F(n) = F(n-1) + F(n-3)

因為牛都不會死，所以會有去年的牛F(n-1),三年前牛的數量，此時都可以生小牛，所以會有F(n-3)這部分。

public class Code_05_Cow {

public static int cowNumber1(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2 || n == 3) {
return n;
}
return cowNumber1(n - 1) + cowNumber1(n - 3);
}

//非遞迴版本
public static int cowNumber2(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2 || n == 3) {
return n;
}
int res = 3;
int pre = 2;
int prepre = 1;
int tmp1 = 0;
int tmp2 = 0;
for (int i = 4; i <= n; i++) {
tmp1 = res;
tmp2 = pre;
res = res + prepre;
pre = tmp1;
prepre = tmp2;
}
return res;
}

public static void main(String[] args) {
int n = 20;
System.out.println(cowNumber1(n));
System.out.println(cowNumber2(n));
}

}

進階

如果每隻母牛隻能活10年，求N年後，母牛的數量。

題目六

給你一個棧，請你逆序這個棧，不能申請額外的資料結構，只能使用遞迴函式。如何實現？

本題考查棧的操作和遞迴函式的設計，我們需要設計出兩個遞迴函式。

遞迴函式一：將棧stack 的棧底元素返回並移除。

具體過程就是如下程式碼中的getAndRemoveLastElement 方法。

如果從stack 的棧頂到棧底依次為3、2、1，這個函式的具體過程如下圖所示。

遞迴函式二：逆序一個棧，就是題目要求實現的方法，具體過程就是如下程式碼中的reverse方法。該方法使用了上面提到的getAndRemoveLastElement 方法。

如果從stack 的棧頂到棧底依次為3、2、1，reverse 函式的具體過程如圖1-5 所示。

getAndRemoveLastElement 方法在圖中簡單表示為get 方法，表示移除並返回當前棧底元素。

public class Code_06_ReverseStackUsingRecursive {

/**
* 以1，2，3為例，從棧頂到棧底依次為3，2，1
*/
public static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
int i = getAndRemoveLastElement(stack);//得到棧底元素
reverse(stack);//遞迴，所以i依次為1，2，3
stack.push(i);//回溯，依次壓入3，2，1
}

//得到棧底元素並它移除，並且其它元素壓回棧
public static int getAndRemoveLastElement(Stack<Integer> stack) {
int result = stack.pop();
if (stack.isEmpty()) {
return result;
} else {
int last = getAndRemoveLastElement(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(test.pop());
}

}

}

題目七

給你一個二維陣列，二維陣列中的每個數都是正數，要求從左上角走到右下角，每一步只能向右或者向下。沿途經過的數字要累加起來。返回最小的路徑和。

沒見過的動態規劃有一個統一的套路，寫出遞迴版本嘗試版本後，得出來的動態規劃的方法是高度套路的。

所有動態規劃都是由暴力版本優化來的。

問題劃分為了：向下或者向右的結果，從中選最小的路徑，就是最後的答案。

//課堂上的程式碼
public static int walk(int[][] matrix, int i, int j) {
int x = matrix.length - 1;
int y = matrix[0].length - 1;
if (i == x && j == y) {
return matrix[i][j];
}
if (i == x)//如果i到達行底部，只能向右走。
return matrix[i][j] + walk(matrix, i, j + 1);

if (j == y)//如果j到達列邊界，只能向下走。
return matrix[i][j] + walk(matrix, i + 1, j);
//其他情況，需要對向下和向右進行對比，選出最優解
int right = walk(matrix, i, j + 1);
int down = walk(matrix, i + 1, j);
return matrix[i][j] + Math.min(right, down);

}

暴力列舉有待優化：有大量的重複解產生，很多部分都重複計算。

把重複計算的部分快取起來，重複的時候直接呼叫就能省時間。

什麼樣的嘗試版本遞迴可以改成動態規劃？

當把遞迴過程展開，發現有重複的狀態，與到達它的路徑是沒有關係的，那麼它一定能改成動態規劃（無後效性問題）。

有後效性的是，漢羅塔、N皇后問題（前面的舉動會影響後面的結果）。

準備一個dp表

1、把需要的位置點出來

2、回到base case中把不被依賴的位置設定好（這題是最後一行/列），然後分析普遍位置是怎麼依賴的（需要哪些位置的幫助），反過去就是整個計算順序。依次計算，推到頂部就是答案。

類似一個搭積木的過程，堆積到一定條件就能出現答案。

public class Code_07_MinPath {

public static int minPath1(int[][] matrix) {
return process1(matrix, matrix.length - 1, matrix[0].length - 1);
}

//從{i,j}出發，到達最右下角位置，最小路徑和是多少？
public static int process1(int[][] matrix, int i, int j) {
int res = matrix[i][j];
if (i == 0 && j == 0) {
return res;
}
if (i == 0 && j != 0) {
return res + process1(matrix, i, j - 1);
}
if (i != 0 && j == 0) {
return res + process1(matrix, i - 1, j);
}
return res + Math.min(process1(matrix, i, j - 1), process1(matrix, i - 1, j));
}

//動態規劃
public static int minPath2(int[][] m) {
if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
return 0;
}
int row = m.length;
int col = m[0].length;
int[][] dp = new int[row][col];
dp[0][0] = m[0][0];
//第一列賦值
for (int i = 1; i < row; i++) {
dp[i][0] = dp[i - 1][0] + m[i][0];
}
//第一行賦值
for (int j = 1; j < col; j++) {
dp[0][j] = dp[0][j - 1] + m[0][j];
}
//最優賦值
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
}
}
return dp[row - 1][col - 1];
}

// for test
public static int[][] generateRandomMatrix(int rowSize, int colSize) {
if (rowSize < 0 || colSize < 0) {
return null;
}
int[][] result = new int[rowSize][colSize];
for (int i = 0; i != result.length; i++) {
for (int j = 0; j != result[0].length; j++) {
result[i][j] = (int) (Math.random() * 10);
}
}
return result;
}

//課堂上的程式碼
public static int walk(int[][] matrix, int i, int j) {
int x = matrix.length - 1;
int y = matrix[0].length - 1;
if (i == x && j == y) {
return matrix[i][j];
}
if (i == x)//如果i到達行底部，只能向右走。
return matrix[i][j] + walk(matrix, i, j + 1);

if (j == y)//如果j到達列邊界，只能向下走。
return matrix[i][j] + walk(matrix, i + 1, j);
//其他情況，需要對向下和向右進行對比，選出最優解
int right = walk(matrix, i, j + 1);
int down = walk(matrix, i + 1, j);
return matrix[i][j] + Math.min(right, down);

}


public static void main(String[] args) {
int[][] m = {{1, 3, 5, 9}, {8, 1, 3, 4}, {5, 0, 6, 1}, {8, 8, 4, 0}};
System.out.println(minPath1(m));
System.out.println(minPath2(m));

m = generateRandomMatrix(6, 7);
System.out.println(minPath1(m));
System.out.println(minPath2(m));
}
}

題目八

給你一個數組arr，和一個整數aim。如果可以任意選擇arr中的數字，能不能累加得到aim，返回true或者false

這是一個無後效性問題。可以使用dp，不管之前做了什麼選擇，只要是之前的累加和、步數是固定的，返回值一定確定。

i就是陣列長度，sum的範圍是全部數的和。

首先檢視遞迴的base case，分析出最後一行，只有aim對應的列是T其餘全是F，通過檢視遞迴的規律，普遍的位置依賴的是兩種情況，[i+1,sum]和[i+1,sum+arr[i]]，逐個計算把整個dp陣列填滿。如果aim超出sum ，那肯定是計算不出來的，因為sum是陣列全部數加起來的和。

最後計算出[0,0]的位置，可以直接返回。

和題意沒關係了。（從暴力遞迴中總結出來）

有負數怎麼辦？要設計一下

public class Code_08_Money_Problem {

public static boolean money1(int[] arr, int aim) {
return process1(arr, 0, 0, aim);
}

public static boolean process1(int[] arr, int i, int sum, int aim) {
if (sum == aim)
return true;

// sum != aim
if (i == arr.length)
return false;

return process1(arr, i + 1, sum, aim) || process1(arr, i + 1, sum + arr[i], aim);
}

public static boolean money2(int[] arr, int aim) {
boolean[][] dp = new boolean[arr.length + 1][aim + 1];
for (int i = 0; i < dp.length; i++) {
dp[i][aim] = true;//以目標金額為列的肯定為true
}
for (int i = arr.length - 1; i >= 0; i--) {//從最後一行開始
for (int j = aim - 1; j >= 0; j--) {//aim往後的都超過，沒必要看
dp[i][j] = dp[i + 1][j];//通過直接的下方的判斷。
if (j + arr[i] <= aim) {//如果該數加上arr[i](當前可以累加的數)少於等於目標數。
// 有可能可行，通過檢視加上了arr[i](當前可以累加的數)的狀態來判斷
dp[i][j] = dp[i][j] || dp[i + 1][j + arr[i]];
}
}
}
return dp[0][0];
}

public static boolean check(int[] arr,int i,int sum,int aim){
if (i == arr.length){//判斷是否走到最後一步
return sum == aim;
}
return check(arr,i+1,sum,aim) || check(arr,i+1,sum+arr[i],aim);
}



public static void main(String[] args) {
int[] arr = { 1, 4, 8 };
int aim = 12;
//System.out.println(money1(arr, aim));
//System.out.println(money2(arr, aim));

System.out.println(check(arr,0,0,aim));

}

}

題目九

給定兩個陣列w和v，兩個陣列長度相等，w[i]表示第i件商品的重量，v[i]表示第i件商品的價值。再給定一個整數bag，要求你挑選商品的重量加起來一定不能超過bag，返回滿足這個條件下，你能獲得的最大價值。

public class Code_09_Knapsack {

public static int maxValue1(int[] c, int[] p, int bag) {
return process1(c, p, 0, 0, bag);
}

public static int process1(int[] weights, int[] values, int i, int alreadyweight, int bag) {
if (alreadyweight > bag) {
return 0;
}
if (i == weights.length) {
return 0;
}
//每次就兩種情況：1、不拿商品 2、拿商品承擔重量
return Math.max(
process1(weights, values, i + 1, alreadyweight, bag),
values[i] + process1(weights, values, i + 1, alreadyweight + weights[i], bag));
}
//carat 克拉/重量price 價值
public static int maxValue2(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--) {//超過bag將毫無意義
dp[i][j] = dp[i + 1][j];
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 void main(String[] args) {
int[] c = { 3, 2, 4, 7 };
int[] p = { 5, 6, 3, 19 };
int bag = 11;
System.out.println(maxValue1(c, p, bag));
System.out.println(maxValue2(c, p, bag));
}

}

演算法初級面試題08——遞迴和動態規劃的精髓、階乘、漢諾塔、子序列和全排列、母牛問題、逆序棧、最小的路徑...

題目一

題目二

題目三

題目四

題目五

題目六

題目七

題目八

題目九

您可能也會喜歡…