第18節

題目1：漢諾塔問題（變體）

體系學習班18節有講暴力遞歸的漢諾塔原題。

給定一個數組arr，長度為N，arr中的值只有1，2，3三種

arr[i] == 1，代表漢諾塔問題中，從上往下第i個圓盤目前在左

arr[i] == 2，代表漢諾塔問題中，從上往下第i個圓盤目前在中

arr[i] == 3，代表漢諾塔問題中，從上往下第i個圓盤目前在右

那么arr整體就代表漢諾塔游戲過程中的一個狀況

如果這個狀況不是漢諾塔最優解運動過程中的狀況，返回-1

如果這個狀況是漢諾塔最優解運動過程中的狀況，返回它是第幾個狀況（而不是還剩幾個狀況）

思路

對于傳統的漢諾塔問題，如果我要將 123456 從最左邊的柱子上移動到最右邊的柱子上，需要分成三大步：

【第一大步】將 12345 從左邊的柱子移動到中間的位置
【第二大步】將 6 從左邊的柱子移動到右邊的位置
【第三大步】將 12345 從中間的位置移動到右邊的位置

上述傳統問題的解法是，定義遞歸函數 f(i, from, to, other)，表示將 [0~i] 的圓盤從 from 柱子移動到 to 柱子上，另外那個柱子叫 other。

對于本題，需要明確一下題意，有幾個已知條件：

漢諾塔問題，最優解是唯一的路徑。
題目中給的過程狀態，如果不在唯一路徑上，就返回-1。
舉個極端的例子，1層漢諾塔問題，把1從最左邊的柱子上移動到最右邊的柱子上，只要一步就可以了。而”1在中間這個柱子上“這個狀態，就是一個不在最優解路徑上的例子。

本題的解法是，定義遞歸函數int step(int[] arr, int i, int from, int to, int other)，表示當前來到 arr 狀態下，將 [0~i] 的圓盤從 from 柱子移動到 to 柱子上，另外那個柱子叫 other，返回至少需要幾步。

public static int kth(int[] arr) {int N = arr.length;return step(arr, N - 1, 1, 3, 2);
}// 我的疑問：arr為什么全程不更新？
// 自問自答：因為返回它當前走到了第幾個狀況，而不是還剩幾個狀況。
public static int step(int[] arr, int index, int from, int to, int other) {if (index == -1) {return 0;}if (arr[index] == other) { // 最大的數字只可能在from或者to的底部，不可能在other上return -1;}// arr[index]的值，剩下兩種情況：// 情況1：arr[index] == from// 情況2：arr[index] == toif (arr[index] == from) { // 情況1：如果index號圓盤還在from上，說明上述連【第一大步】都沒走完// 因為我只想知道當前已經走過多少步了，所以只要統計在【第一大步】中走了多少步就可以了，后面的【第二大步】【第三大步】肯定根本沒走// 怎么統計呢？我們知道【第一大步】的目標是將[0~i-1]從from挪到other上，而且當前已經走到arr狀態了，所以就這樣繼續遞歸return step(arr, index - 1, from, other, to);} else { // 情況2：如果index號圓盤已經在to上了，說明已經完成[0~index-1]的漢諾塔問題了// 【第一大步】已經完成的從[0~index-1]范圍上的index層漢諾塔問題需要的步驟數（n層漢諾塔，最優解2^n-1步）int p1 = (1 << index) - 1; // 【第二大步】已經將index號圓盤從from挪到to了，因為我們從arr中看到index號圓盤已經在to上了int p2 = 1; // 【第三大步】當前正在經歷的，將[0~i-1]號圓盤從other挪到to上，在arr狀態下，統計已經走過多少步了？int p3 = step(arr, index - 1, other, to, from); // 如果發現它的子問題根本就不是最優解的某一步，直接返回-1if (p3 == -1) { return -1;}return p1 + p2 + p3;}
}

題目2：兩個島嶼的距離，“感染”問題

Leetcode 原題：

https://leetcode.com/problems/shortest-bridge/

我在力扣上的自己寫的答案：

class Solution {int m, n;public static final int offset = 100;public int shortestBridge(int[][] grid) {m = grid.length;n = grid[0].length;// 將其中一個島A加offset，用來區分兩個島label:for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {incr(grid, i, j);break label; // 中斷所有循環，回到label處，但并不重新進入循環}}}// 左上角主動感染，右下角原地不動int term = offset;while (true) {boolean[][] seen = new boolean[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == term && !seen[i][j]) {int result = process(grid, i, j, term, seen);if (result != Integer.MAX_VALUE) return result - offset;}}}term++;}}// 當前島嶼向外感染public int process(int[][] grid, int i, int j, int term, boolean[][] seen) {int result = Integer.MAX_VALUE;if (i < 0 || i == m || j < 0 || j == n || seen[i][j]) return result; // 越界，或重復路線seen[i][j] = true;if (grid[i][j] == 0) { // 當前位置未感染，則感染grid[i][j] = term + 1;} else if (grid[i][j] == term) { // 當前位置是感染源，則去感染周圍result = Math.min(result, process(grid, i + 1, j, term, seen));result = Math.min(result, process(grid, i - 1, j, term, seen));result = Math.min(result, process(grid, i, j + 1, term, seen));result = Math.min(result, process(grid, i, j - 1, term, seen));} else if (grid[i][j] == 1) { // 兩島接壤，則快速返回return term;}return result;}// 給其中一個島加offsetpublic void incr(int[][] grid, int i, int j) {if (i < 0 || i == m || j < 0 || j == n) return;if (grid[i][j] == 1) {grid[i][j] = offset;incr(grid, i + 1, j);incr(grid, i - 1, j);incr(grid, i, j + 1);incr(grid, i, j - 1);}}
}

題目3：最大路徑和

牛客網原題：

https://www.nowcoder.com/questionTerminal/8ecfe02124674e908b2aae65aad4efdf

給定一個矩陣matrix，先從左上角開始，每一步只能往右或者往下走，走到右下角。然后從右下角出發，每一步只能往上或者往左走，再回到左上角。任何一個位置的數字，只能獲得一遍。返回最大路徑和。

輸入描述

第一行輸入兩個整數M和N，M,N<=200
接下來M行，每行N個整數，表示矩陣中元素5 10
1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1
1 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1

輸出描述

輸出一個整數，表示最大路徑和16

思路

第一次見到這題，是在體系學習班第14節。當時只講了不能貪心，應該用dp，但沒有細說。

黃色部分表示我想要拿到的位置：

在這里插入圖片描述

錯誤的貪心路徑

少拿一個灰色的格子。
在這里插入圖片描述

正確的路徑

最好情況下，能夠拿到所有的格子。

在這里插入圖片描述

雖然題目要求是一來一回，但我們可以想象成有兩個人 a、b，都從左上角走到右下角，求整個過程中，最多能拿到多少值。

內存超限版本如下。其實可以省掉一個維度就不會超了，因為(i1, j1), (i2, j2) 兩個坐標中，存在關系：i1+j1=i2+j2。可變參數數量能省則省！

import java.util.Scanner;// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {static int[][] arr;public static void main(String[] args) {Scanner in = new Scanner(System.in);int m = in.nextInt();int n = in.nextInt();arr = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {arr[i][j] = in.nextInt();}}int[][][][] dp = new int[m][n][m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {for (int k = 0; k < m; k++) {for (int l = 0; l < n; l++) {dp[i][j][k][l] = -1;}}}}int res = process(0, 0, 0, 0, dp);System.out.println(res);}// 當前a在i1,j1位置，b在i2,j2位置// 兩個人都只能向右走或者向下走，求能拿到的最多點數public static int process(int i1, int j1, int i2, int j2, int[][][][] dp) {if (i1 == arr.length || j1 == arr[0].length) return 0;if (i2 == arr.length || j2 == arr[0].length) return 0;if (dp[i1][j1][i2][j2] >= 0) return dp[i1][j1][i2][j2];// a,b如果走到了同一個位置，點數只能累加一次int res = arr[i1][j1];if (i1 != i2 && j1 != j2) res += arr[i2][j2];// a向右，b向右int p1 = process(i1 + 1, j1, i2 + 1, j2, dp);// a向下，b向下int p2 = process(i1, j1 + 1, i2, j2 + 1, dp);// a向右，b向下int p3 = process(i1, j1 + 1, i2 + 1, j2, dp);// a向下，b向右int p4 = process(i1 + 1, j1, i2, j2 + 1, dp);res += Math.max(Math.max(p1, p2), Math.max(p3, p4));dp[i1][j1][i2][j2] = res;return res;}
}
/*5 10
1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1
1 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 1 1 12 2
1 1
1 1*/