记忆化搜索
什么是记忆化搜索
本质是动态规划，动态规划就是解决了重复计算的搜索。
动态规划的实现方式：
- 循环（从小到大递推）
- 记忆化搜索（从大到小搜索）
- 画搜索树
什么时候使用？
- 递推不方便使用，递推不是顺序性的，比如从左上到右下。状态转移特别麻烦，不是顺序性。
- 初始化状态不好找（起点不好找）。
- 从大到小
区间类DP
- 求一段区间的min/max/count
- 转移方程通过区间来更新
- 从大到小的更新
在动态变化的数组中，变化的也并不是状态，而只是子状态的范围，即记忆化搜索中的 (start, end). 区间类dp的核心是如何在动态变化的数组中，依然正确定义并计算 subproblem.
329. Longest Increasing Path in a Matrix
Given an integer matrix, find the length of the longest increasing path.
Example 1:
nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]
Return 4 The longest increasing path is [1, 2, 6, 9].
思路：
初始状态不好找，而且状态转移是上下左右四个方向的，所以用递推的方式不好做。
state: dp[i][j] 以i,j 为结尾的最长子序列
function: 遍历上下左右四个格子
Initilize: dp[i][j] = 1
Answer: 最大值
难点：如何加速搜索的过程，用一个mem矩阵记录已经计算过的中间结果，避免重复运算。
因为要对上下左右四个方位进行搜索，所以可以用
dx[] = {1,-1,0,0} 和 dy[] = {0,0, 1,-1}来循环上下左右四个方向。
我们需要维护一个二维动态数组dp，其中dp[i][j]表示数组中以(i,j)为起点的最长递增路径的长度，初始将dp数组都赋为0。
当我们用递归调用时，遇到某个位置(x, y), 如果dp[x][y]不为0的话，我们直接返回dp[x][y]即可，不需要重复计算。我们需要以数组中每个位置都为起点调用递归来做，比较找出最大值。在以一个位置为起点用DFS搜索时，对其四个相邻位置进行判断，如果相邻位置的值大于上一个位置，则对相邻位置继续调用递归，并更新一个最大值，搜素完成后返回即可。
takeaway: 记忆化搜索方法 for循环实现四个方向的搜索 return 什么value?
code
public class Solution {
int[] dx = {0,1,0,-1};
int[] dy = {1,0,-1,0};
public int longestIncreasingPath(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int m = matrix.length;
int n = matrix[0].length;
int max = 0;
// flag
int[][] flag = new int[m][n];
// dp, 到当前节点为终点最长的path 有多长
int[][] dp = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
max = Math.max(max, search(matrix, i, j, flag, dp));
}
}
return max;
}
public int search(int[][] matrix, int i, int j, int[][] flag, int[][] dp) {
if(flag[i][j] != 0) {
return dp[i][j];
}
flag[i][j] = 1;
// init
int result = 1;
for(int k = 0; k < 4; k++) {
int ni = i + dx[k];
int nj = j + dy[k];
if(ni >= 0 && nj >= 0 && ni < matrix.length && nj < matrix[0].length && matrix[ni][nj] < matrix[i][j]) {
result = Math.max(result, search(matrix, ni, nj, flag, dp) + 1);
}
}
dp[i][j] = result;
return result;
}
}
Stone Game
At the beginning of the game the player picks n piles of stones in a line.
The goal is to merge the stones in one pile observing the following rules:
At each step of the game,the player can merge two adjacent piles to a new pile. The score is the number of stones in the new pile. You are to determine the minimum of the total score.
Example:
For [4, 1, 1, 4], in the best solution, the total score is 18:
1. Merge second and third piles => [4, 2, 4], score +2
2. Merge the first two piles => [6, 4]，score +6
3. Merge the last two piles => [10], score +10
分析
很容易就想到一个贪心的做法，那就是每次都去找两个代价最小的石子来合并。
但其实这是不对的，反例：[6,4,4,6]
一般的贪心做法很容易错的，没思路的话可以先从穷举搜索开始入手，然后优化（剪枝，加cache）。
为什么要用区间型动态规划，因为一个变量不好区分状态，需要两个变量来区分不同的状态。而且从小到大不太好想，但是从大到小比较好实现，因为长度固定（合并方式）。
• 死胡同:容易想到的一个思路从小往大，枚举第一次合并是在哪? • 记忆化搜索的思路，从大到小，先考虑最后的 0,n-1 合并的总花费
State:
dp[i][j] 表示把第i到第j个石子合并到一起的最小花费
Function:
预处理sum[i,j] 表示i到j所有石子价值和
dp[i][j] = min(dp[i][k]+dp[k+1][j]+sum[i,j]) 对于所有k属于{i,j}
k 就相当于枚举合并的分割线。
Intialize:
for each i, dp[i][i] = 0
Answer:
dp[0][n-1]
Time: O(n^2 * n)
Code
public class Solution {
public int stoneGame(int[] A) {
if(A == null || A.length == 0) {
return 0;
}
int n = A.length;
int[][] dp = new int[n][n];
boolean[][] visit = new boolean[n][n];
// i - j sum of piles of stones 预处理，把两堆石子合并到一起花费的代价
int[][] sum = new int[n][n];
for(int i = 0; i < n; i++) {
sum[i][i] = A[i];
for(int j = i + 1; j < n; j++) {
sum[i][j] = sum[i][j - 1] + A[j];
}
}
return dfs(0, n - 1, dp, visit, sum);
}
public int dfs(int i, int j, int[][] dp, boolean[][] visit, int[][] sum) {
if(visit[i][j]) {
return dp[i][j];
}
visit[i][j] = true;
// base case
if(i >= j) {
return 0;
}
dp[i][j] = Integer.MAX_VALUE;
// 枚举分割线， 从大到小看
for(int k = i; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dfs(i, k, dp, visit, sum) + dfs(k + 1, j, dp, visit, sum) + sum[i][j]);
}
return dp[i][j];
}
}
312. Burst Balloons (Snapchat)
Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] nums[i] nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
Note: (1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them. (2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:
Given [3, 1, 5, 8]
Return 167
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
分析
放弃贪心，局部最优，难想而且容易错。
自大往小想，就是从最后的的状态出发，枚举 最后打爆的气球。 其实也就是Divide and conquer 加 cache。
State: 大状态
dp[i][j] 表示把第i个到第j个气球打爆的最大的价值
Function:
所有k属于{i,j}, k是最后打爆的气球
midValue = arr[i - 1] * arr[k] * a[j + 1]
dp[i][j] = max{dp[i][k - 1] + dp[k + 1][j] + midValue}
Init:
dp[i][i] = arr[i - 1] * arr[i] * arr[i + 1]
Answer:
dp[0][n - 1]
Code
// Time: O(n^3)
public class Solution {
public int maxCoins(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
boolean[][] visit = new boolean[n + 2][n + 2];
// dp[i][j] 表示把第i个到第j个气球打爆的最大的价值
int[][] dp = new int[n + 2][n + 2];
// add two dummy node at the start and end
int[] A = new int[n + 2];
for(int i = 1; i <= n; i++) {
A[i] = nums[i - 1];
}
A[0] = 1;
A[n + 1] = 1;
return dfs(A, 1, n, visit, dp);
}
public int dfs(int[] A, int s, int e, boolean[][] visit, int[][] dp) {
if(visit[s][e]) {
return dp[s][e];
}
// memo
visit[s][e] = true;
int max = 0;
// 枚举最后打爆的气球i
for(int i = s; i <= e; i++) {
int mid = A[s - 1] * A[i] * A[e + 1]; // 最后打爆，init
int left = dfs(A, s, i - 1, visit, dp);
int right = dfs(A, i + 1, e, visit, dp);
max = Math.max(max, mid + left + right);
}
dp[s][e] = max;
return dp[s][e];
}
}