33.递归、搜索、回溯之记忆化搜索

1.斐波那契数（easy）

. - 力扣（LeetCode）

题目解析

斐波那契数列

算法原理

解法一：递归

解法二：记忆化搜索

【另一种形式的剪枝】

【带备忘录的递归】

 代码

解法三：动态规划

代码 

2.不同路径

. - 力扣（LeetCode）

题目解析

算法原理

代码

class Solution {public int uniquePaths(int m, int n) {// 动态规划int[][] dp = new int[m + 1][n + 1];dp[1][1] = 1;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++) {if (i == 1 && j == 1)continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}return dp[m][n];// 记忆化搜索// int[][] memo = new int[m + 1][n + 1];// return dfs(m, n, memo);}public int dfs(int i, int j, int[][] memo) {if (memo[i][j] != 0) {return memo[i][j];}if (i == 0 || j == 0)return 0;if (i == 1 && j == 1) {memo[i][j] = 1;return 1;}memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);return memo[i][j];}
}

3.最长递增子序列

. - 力扣（LeetCode）

题目解析

算法原理

代码

class Solution {public int lengthOfLIS(int[] nums) {int n = nums.length;int[] dp = new int[n];int ret = 0;Arrays.fill(dp, 1);// 填表顺序: 从后往前for (int i = n - 1; i >= 0; i--) {for (int j = i + 1; j < n; j++) {if (nums[j] > nums[i]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}ret = Math.max(ret, dp[i]);}return ret;// 记忆化搜索// int ret = 0;// int n = nums.length;// int[] memo = new int[n];// for(int i = 0; i < n; i++)// {// ret = Math.max(ret, dfs(i, nums, memo));// }// return ret;}public int dfs(int pos, int[] nums, int[] memo) {if (memo[pos] != 0)return memo[pos];int ret = 1;for (int i = pos + 1; i < nums.length; i++) {if (nums[i] > nums[pos]) {ret = Math.max(ret, dfs(i, nums, memo) + 1);}}memo[pos] = ret;return ret;}
}

4.猜数字大小II

. - 力扣（LeetCode）

题目解析

算法原理

代码

class Solution {int[][] memo;public int getMoneyAmount(int n) {memo = new int[n + 1][n + 1];return dfs(1, n);}public int dfs(int left, int right) {if (left >= right)return 0;if (memo[left][right] != 0) {return memo[left][right];}int ret = Integer.MAX_VALUE;for (int head = left; head <= right; head++) {int x = dfs(left, head - 1);int y = dfs(head + 1, right);ret = Math.min(Math.max(x, y) + head, ret);}memo[left][right] = ret;return ret;}
}

5.矩阵中的最长递增路径

. - 力扣（LeetCode）

题目解析

算法原理

代码

class Solution {int m, n;int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };int[][] memo;public int longestIncreasingPath(int[][] matrix) {m = matrix.length;n = matrix[0].length;memo = new int[m][n];int ret = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)ret = Math.max(ret, dfs(matrix, i, j));return ret;}public int dfs(int[][] matrix, int i, int j) {if (memo[i][j] != 0) {return memo[i][j];}int ret = 1;for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {ret = Math.max(ret, dfs(matrix, x, y) + 1);}}memo[i][j] = ret;return ret;}
}