大家好，我是晴天學長，記憶化搜索，找到技巧非常重要，需要的小伙伴可以關注支持一下哦！后續會繼續更新的。💪💪💪

2) .算法思路

1.memo三維表示記錄的結果

---

3）.算法步驟

1.首先導入需要的類和包，包括 java.util.Scanner。
2.創建一個公共類 Main。
3.聲明一個靜態變量 mod 并初始化為 1000000007，用于取模操作。
4.聲明一個三維數組 memo，用于存儲中間計算結果。
5.在 main 方法中，創建一個 Scanner 對象來讀取輸入。
6.通過 scanner.nextInt() 方法分別讀取輸入的 N 和 M 的值。
7.初始化變量 sum 為 2。
8.創建大小為 101x101x101 的 memo 數組，并將其所有元素初始化為 -1。
9.調用 dfs 方法，并將 sum、N 和 M 作為參數傳遞給它。
10.在控制臺打印輸出 dfs 方法的返回值。
11.定義 dfs 方法，接收 sum、N 和 M 作為參數。
12.首先進行遞歸終止條件的判斷，如果 sum 等于 1，N 等于 0，M 等于 1，返回 1。
13.進行剪枝操作，如果 sum 小于 0，N 小于 0 或 M 小于 0，返回 0。
14.如果 sum 大于 M，返回 0。
15.檢查 memo[sum][N][M] 是否已經計算過，如果有值，則直接返回該值。
16.如果沒有計算過，進行遞歸計算并將結果保存到 memo 數組中。
17.遞歸調用 dfs 方法，傳入 sum*2、N-1 和 M 作為新的參數，并將結果與遞歸調用 dfs 方法，傳入 18.sum-N 和 M-1 作為新的參數的結果相加，并對 mod 取模。
19.將結果保存到 memo 數組中，并返回該值。

---

4）. 代碼實例

import java.util.Scanner;public class Main {static int mod = 1000000007;static int[][][] memo;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int M = scanner.nextInt();int sum = 2;memo = new int[101][101][101];for (int i = 0; i < 101; i++) {for (int j = 0; j < 101; j++) {for (int k = 0; k < 101; k++) {memo[i][j][k] = -1; // 初始化dp數組為-1}}}System.out.println(dfs(sum, N, M));}//口枝葉回//酒喝光了遇到店是合法的,最后一次是定了的private static int dfs(int sum ,int N,int M) {if (sum==1&&N==0&&M==1) {return 1;}//剪枝if (sum<0||N<0||M<0) {return 0;}if (sum > M) return 0;if (memo[sum][N][M]!=-1) {return memo[sum][N][M];}memo[sum][N][M]=(dfs(sum*2, N-1, M)+dfs(sum-1, N,M-1))%mod;return memo[sum][N][M];}
}

---

5）. 總結

• dp和記憶化搜索的熟練掌握。

---