本文主要是介绍记忆化搜索总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
DFS + Memo就是DP，注意cache存的物理意义，因为DFS是top down的，那么都是走到base case了，然后返回，那么存的结果就是从base case来的结果，那么就是存dp[0][0], dp[0][1] .. 一直到dp[n][target]. 最后返回的就是dp[n][ target]，还有个tricky的地方就是表示是否有值和是否访问过，解决方法就是存-1，代表没有访问过，如果是0，就代表是没有解；
Longest Increasing Path in a Matrix dp[i][j] 代表的是以i,j为index的cell，最长的升序长度是多少。然后每个点做dfs，判断四个方向的来的最大值；Time O(M*N) Space: O(M*N);
class Solution {public int longestIncreasingPath(int[][] matrix) {if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {return 0;}int maxlen = 0;int n = matrix.length;int m = matrix[0].length;int[][] cache = new int[n][m];for(int i = 0; i < n; i++) {Arrays.fill(cache[i], -1);}for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {maxlen = Math.max(maxlen, dfs(matrix, i, j, cache));}}return maxlen;}int[][] dirs = {{0,1}, {0,-1}, {-1,0}, {1,0}};private int dfs(int[][] matrix, int x, int y, int[][] cache) {if(x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length) {return 0;}if(cache[x][y] != -1) {return cache[x][y];}int value = 1;for(int[] dir: dirs) {int nx = x + dir[0];int ny = y + dir[1];if(0 <= nx && nx < matrix.length && 0 <= ny && ny < matrix[0].length&& matrix[nx][ny] > matrix[x][y]) {value = Math.max(value, dfs(matrix, nx, ny, cache) + 1);}}cache[x][y] = value;return cache[x][y];}
}Minimum Number of Days to Eat N Oranges 思路：还有个拐点就是：n %2 != 0 n % 3 != 0，那么代表n % 2, n % 3那些点是我们需要一个个吃的；So, the real choice we have is to eat n % 2 oranges one-by-one and then swallow n / 2, or eat n % 3 oranges so that we can gobble 2 * n / 3.
class Solution {public int minDays(int n) {HashMap<Integer, Integer> hashmap = new HashMap<>();return dfs(n, hashmap);}private int dfs(int n, HashMap<Integer, Integer> hashmap) {if(hashmap.containsKey(n)) {return hashmap.get(n);}if(n <= 1) {hashmap.put(n, n);return n;}hashmap.put(n, 1 + Math.min(n % 2 + dfs(n / 2, hashmap), n % 3 + dfs(n / 3, hashmap)));return hashmap.get(n);}
}Minimum Cost to Cut a Stick 思路：注意start，end是代表list里面的index；也是计算区间的范围；加入0，n是为了后面更好的算长度，直接减就可以了；如果长度是1，已经不能分割了，所以为0；不能割，也就没有cost；
class Solution {public int minCost(int n, int[] cuts) {List<Integer> list = new ArrayList<Integer>();list.add(0); list.add(n); // 加入0，n是为了后面更好的算长度，直接减就可以了；for(int cut: cuts) {list.add(cut);}Collections.sort(list);int[][] cache = new int[list.size()][list.size()];return dfs(list, 0, list.size() - 1 , cache);}// start, end 是代表 list里面的index；也是计算区间的范围；private int dfs(List<Integer> list, int start, int end, int[][] cache) {if(start + 1 >= end) { // 如果长度是1，已经不能分割了，所以为0；不能割，也就没有cost；return 0;}if(cache[start][end] > 0) {return cache[start][end];}int value = Integer.MAX_VALUE;for(int k = start + 1; k < end; k++) {// 左边 + 右边 + cost;value = Math.min(value, dfs(list, start, k, cache) + dfs(list, k, end, cache)+ list.get(end) - list.get(start));}cache[start][end] = value;return cache[start][end];}
}Stone Game V 思路：跟 Minimum Cost to Cut a Stick 非常相似；就是求各种区间可能的最大值；DFS + Cache；
class Solution {public int stoneGameV(int[] A) {int n = A.length;int[] prefix = new int[n + 1];prefix[0] = 0;for(int i = 1; i <= n; i++) {prefix[i] = prefix[i - 1] + A[i - 1];}int[][] cache = new int[n][n];return dfs(A, 0, n - 1, cache, prefix);}private int dfs(int[] A, int start, int end, int[][] cache, int[] prefix) {if(start >= end) {return 0;}if(cache[start][end] != 0) {return cache[start][end];}int localmax = 0;for(int k = start; k < end; k++) {int localvalue = 0;int leftsum = getSum(prefix, start, k); int rightsum = getSum(prefix, k + 1, end); if(leftsum > rightsum) {localvalue = rightsum + dfs(A, k + 1, end, cache, prefix);} else if(leftsum < rightsum) {localvalue = leftsum + dfs(A, start, k, cache, prefix);;} else {// leftsum == rightsum;localvalue = leftsum + Math.max(dfs(A, start, k, cache, prefix), dfs(A, k + 1, end, cache, prefix));}localmax = Math.max(localmax, localvalue);}cache[start][end] = localmax;return cache[start][end];}private int getSum(int[] prefix, int i, int j) {return prefix[j + 1] - prefix[i];}
}Maximum Points You Can Obtain from Cards 思路：用记忆化搜索dp来做，O(N^2) ，不能通过；注意base case是k ==1, Math.max(cardPoints[start], cardPoints[end]);
class Solution {public int maxScore(int[] A, int k) {int n = A.length;Integer[][] cache = new Integer[n][n];return dfs(A, 0, n - 1, k, cache);}private int dfs(int[] A, int start, int end, int k, Integer[][] cache) {if(start > end) {return 0;}if(k == 1) {return Math.max(A[start], A[end]);}if(cache[start][end] != null) {return cache[start][end];}int value = Math.max(dfs(A, start + 1, end, k - 1, cache) + A[start],dfs(A, start, end - 1, k - 1, cache) + A[end]);cache[start][end] = value;return cache[start][end];}
}思路2：这个取值是头跟尾巴，那么可以发现没有取走的数，是个连续的区间，而且是个滑动窗口；逆向思维；
我求得totalsum之后，可以去掉没有取走的区间的sum，就是我取的sum；没有取走的sum，可以由滑动窗口求得；O(N);
class Solution {public int maxScore(int[] A, int k) {int n = A.length;int totalsum = 0;for(int a: A) {totalsum += a;}int count = 0;int j = 0;int cursum = 0;int res = 0;for(int i = 0; i < n; i++) {// move j;while(j < A.length && count <= n - k) {if(count == n - k) {break;}cursum += A[j];count++;j++;}// update res;if(count == n - k) {res = Math.max(res, totalsum - cursum);}// move i;cursum -= A[i];count--;}return res;}
}Minimum Insertion Steps to Make a String Palindrome 思路：dp，记忆化搜索，两头相等，啥也不用做，往中间走，两头不等，那么就是子问题，1 + min(循环递归),然后用cache保存中间结果. Time: O(n ^2); space(n^2);
class Solution {public int minInsertions(String s) {if(s == null || s.length() == 0) {return 0;}int n = s.length();Integer[][] cache = new Integer[n][n];return dfs(s, 0, n - 1, cache);}private int dfs(String s, int start, int end, Integer[][] cache) {if(start >= end) {return 0;}if(cache[start][end] != null) {return cache[start][end];}int res = 0;if(s.charAt(start) == s.charAt(end)) {res = dfs(s, start + 1, end - 1, cache);} else {res = Math.min(dfs(s, start, end - 1, cache), dfs(s, start + 1, end, cache)) + 1;}cache[start][end] = res;return cache[start][end];}
}思路：bottom up； 先算小区间，然后算大区间；记住，len是从2开始的；
class Solution {public int minInsertions(String s) {int n = s.length();int[][] dp = new int[n][n];for(int len = 2; len <= n; len++) {for(int i = 0; i + len - 1 < n; i++) {int j = i + len - 1;if(s.charAt(i) == s.charAt(j)) {dp[i][j] = dp[i + 1][j - 1];} else {// s.charAt(i) != s.charAt(j);dp[i][j] = 1 + Math.min(dp[i][j - 1], dp[i + 1][j]);}}}return dp[0][n - 1];}
}Guess Number Higher or Lower II 思路：这题又是记忆化搜索，要求最小的cost to guarantee a win，也就是在所有的解空间里面，去找最小的，但是又要guarantee，也就是说，比如i.....x.....j ，我在[i,j]区间里面猜x，那么为了保证[i....x -1], [x+1, j] 因为我不知道往那边猜，也许高，也许低，那么为了保证我都能赢，那么我就要在两者中取最大的，这样才能保证我能赢。那么dp[i][j] 代表我能够取得胜利的最小cost。那么递推公式就是： dp[i][j] = Min( x + Max(dp[i][x - 1], dp[x + 1][j]) for all x 属于i <= x <= j;
class Solution {public int getMoneyAmount(int n) {int[][] dp = new int[n + 1][n + 1];return dfs(dp, 1, n);}private int dfs(int[][] dp, int start, int end) {if(start >= end) {return 0;}if(dp[start][end] != 0) {return dp[start][end];}int res = Integer.MAX_VALUE;for(int i = start; i <= end; i++) {res = Math.min(res, i + Math.max(dfs(dp, start, i - 1) , dfs(dp, i + 1, end)));}dp[start][end] = res;return dp[start][end];}
}这题也可以buttom up
class Solution {public int getMoneyAmount(int n) {int[][] dp = new int[n + 1][n + 1];for(int len = 2; len <= n; len++) {// 因为返回的是dp[1][n]，所以i从1开始；for(int i = 1; i + len - 1 <= n; i++) {int j = i + len - 1;dp[i][j] = Integer.MAX_VALUE;// i...k...jfor(int k = i; k < j; k++) {dp[i][j] = Math.min(dp[i][j], k + Math.max(dp[i][k - 1], dp[k + 1][j]));}}}return dp[1][n];}
}Stone Game 思路：区间型动态规划，f[i][j] 表示的物理意义是：面对i 到j的石头，下棋子的人，我可以拿到的最大的与对手的数字差 f[i][j] = max {a[i] - f[i + 1][j], a[j] - f[i][j - 1]} , 最后如果f[0][n - 1] >= 0 代表先手alex能够拿到正数，也就是比lee拿得多，从而赢；
初始化： f[i][i] = a[i], 就面对一个数字；
计算顺序：
长度1： f[0][0] f[1][1] f[2][2]....f[n - 1][n - 1]
长度2：f[0][1],.....f[n - 2][n-1]
...
长度N：f[0][n - 1]
class Solution {public boolean stoneGame(int[] A) {int n = A.length;int[][] dp = new int[n][n];for(int i = 0; i < n; i++) {dp[i][i] = A[i];}// len == 1,已经计算过了；for(int len = 2; len <= n; len++) {for(int i = 0; i + len - 1 < n; i++) {int j = i + len - 1;dp[i][j] = Math.max(A[i] - dp[i + 1][j], A[j] - dp[i][j - 1]);}}return dp[0][n - 1] > 0;}
}思路2：看了花花的视频，感觉还是min-max的思路，dfs+memo cache比较好理解，比较好想。
score(A, l, r)代表面对 s[l]...s[r] 区间，我能够取得的相对的最大值，也就是我的值减去对手的值，要最大；博弈型都是相互min对方的解，max自己的解； 不用cache，会超时TLE; 加入cache, O(N^2) ，因为总共有r, l N^2个解，每个解用了cache就是O(1)，所以就是O(N^2).
class Solution {public boolean stoneGame(int[] A) {int n = A.length;int[][] cache = new int[n][n];return dfs(A, 0, n - 1, cache) > 0;}private int dfs(int[] A, int start, int end, int[][] cache) {if(start > end) {return 0;}if(start == end) {return A[start];}if(cache[start][end] != 0) {return cache[start][end];}cache[start][end] = Math.max(A[start] - dfs(A, start + 1, end, cache),A[end] - dfs(A, start, end - 1, cache));return cache[start][end];}
}Stone Game II 思路：这题用记忆化递归做，比较好做；score代表的物理意义是以i为起点，我面对i ~ n - 1个石头的，我能够取到的最大值，也就是相对最大值，后面的sum 减去对手能够得到的最大值；这里有一维参数M，每次传下去的是Max(M, x) 因为下次我可以取[1,2*M]个数；
class Solution {public int stoneGameII(int[] A) {if(A == null || A.length == 0) {return 0;}int n = A.length;int[] suffixSum = new int[n + 1]; // 从后往前计算，i ~ n -1的和，因为我是求后面的和；suffixSum[n] = 0;for(int i = n - 1; i >= 0; i--) {suffixSum[i] = suffixSum[i + 1] + A[i];}int[][] cache = new int[n][n];return dfs(A, suffixSum, 0, 1, cache);}private int dfs(int[] A, int[] suffixSum, int i, int M, int[][] cache) {if(i == A.length) {return 0;}if(cache[i][M] != 0) {return cache[i][M];}if(i + 2 * M >= A.length){ // 如果i + 2*M 已经>= A.length, 取剩下所有的；return suffixSum[i];}int value = 0;for(int x = 1; x <= 2*M; x++) {value = Math.max(value, suffixSum[i] - dfs(A, suffixSum, i + x, Math.max(M, x), cache));}cache[i][M] = value;return cache[i][M];}
}Cherry Pickup 思路：这题比较迷惑，从左往右，然后再返回到0，其实可以理解成有两个人同时从(n-1, n-1)往(0,0)走，两个人同步。这样就有(x1, y1) (x2, y2)，同步也就是x1 + y1 = x2 + y2;，那么y2坐标即使可以= x1+y1 - x2，那么dp的状态就是：在x1,y1,x2,y2的时候，可以得到的最大的cherry是多少。那么这题可以用dfs + memory search来解决；
(x1,y1), (x2, y2) 可以分别走上面和左边，那么就有四个点可以走，
2 (x1-1,y1) 3 (x2 -1, y2)
1 (x1, y1-1) (x1,y1) 4 (x2, y2 -1) (x2, y2)
那么就有4种组合。(1,3), (1,4), (2,3),( 2,4) 这题注意，两个同时在一个点的时候，只能1个人取，两个人分别的时候，可以分别取；
这题让我理解到：还是回归到了dp的解题步骤，最后一步，假设都做完了，就剩下最后一步，中间用矩阵去存中间的状态，然后倒数第二步往最后一步走，倒数第二步所有状态里面取最大，然后往前走一步；
class Solution {public int cherryPickup(int[][] grid) {if(grid == null || grid.length == 0 || grid[0].length == 0) {return 0;}int n = grid.length;int[][][] dp = new int[n][n][n];for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {for(int k = 0; k < n; k++) {dp[i][j][k] = Integer.MIN_VALUE;}}}return Math.max(0, dfs(grid, dp, n - 1, n - 1, n - 1));}private int dfs(int[][] grid, int[][][] dp, int x1, int y1, int x2) {int y2 = x1 + y1 - x2;if(x1 < 0 || y1 < 0 || x2 < 0 || y2 < 0) {return -1;}if(dp[x1][y1][x2] != Integer.MIN_VALUE) {return dp[x1][y1][x2];}if(x1 == 0 && y1 == 0) {return grid[0][0];}if(grid[x1][y1] == -1 || grid[x2][y2] == -1) {dp[x1][y1][x2] = -1;return -1;}int value = 0;value = Math.max(Math.max(dfs(grid, dp, x1, y1 - 1, x2), dfs(grid, dp, x1, y1 - 1, x2 - 1)),Math.max(dfs(grid, dp, x1 - 1, y1, x2), dfs(grid, dp, x1 - 1, y1, x2 - 1)));// 从上面四种状态来到当前格子；if(value < 0) {dp[x1][y1][x2] = -1; // 记住，状态一定要记住，然后返回；return -1;}value += grid[x1][y1];if(x1 != x2 && y1 != y2) {// 如果两个坐标点不一样，则可以加入两个value;value += grid[x2][y2];}dp[x1][y1][x2] = value;return dp[x1][y1][x2];}
}Cherry Pickup II 思路：top down dp，想最后一步，两个机器人假设从 1 ~ n - 1全部已经搞定了，那么从当前往下，会有9种可能，下去。取9种可能性里面最大的，往下走。如果c1 == c2, 那么就加一个值，如果c1 != c2, 那么 就收集两个，加两个cell的值；注意dp array是三维的，而且是用Integer来表示，可以dp[row][c1][c2] != null, return;
class Solution {public int cherryPickup(int[][] grid) {if(grid == null || grid.length == 0 || grid[0].length == 0) {return 0;}int m = grid.length;int n = grid[0].length;int[][][] cache = new int[m][n][n];return dfs(grid, 0, 0, n - 1, cache, m, n);}private int dfs(int[][] grid, int row, int col1, int col2, int[][][] cache, int m, int n) {if(row == m) {return 0;}if(cache[row][col1][col2] != 0) {return cache[row][col1][col2];}int value = 0;for(int i = -1; i <= 1; i++) {for(int j = -1; j <= 1; j++) {int ncol1 = col1 + i;int ncol2 = col2 + j;if(0 <= ncol1 && ncol1 < n && 0 <= ncol2 && ncol2 < n) {value = Math.max(value, dfs(grid, row + 1, ncol1, ncol2, cache, m, n));}}}// 最后一步，从9个状态里面最大的那个来到当前的格子,[row][col1][col2];value += grid[row][col1];if(col1 != col2) {value += grid[row][col2];}cache[row][col1][col2] = value;return cache[row][col1][col2];}
}Number of Ways to Stay in the Same Place After Some Steps 思路：还是由最后一步得到，三种状态Right, left, stay三种状态最后一步得到最后status，i表示index，remain代表还剩下多少步，memo[i][j] 代表的是index为i的情况下，我还有remain步的情况下，总共可能的情况有多少种。如果，index > remainstep，肯定回不来直接return 0；base case是index == 0, remainstep == 0, return 1;
class Solution {int MOD = 1000000007;public int numWays(int steps, int arrLen) {long[][] cache = new long[steps + 1][steps + 1];return (int)dfs(cache, 0, steps, arrLen);}private long dfs(long[][] cache, int index, int remain, int arrLen) {// 一定不要忘记，i == 0, remain == 0的时候，返回1，代表就这一种状态；不用走了if(index == 0 && remain == 0) {return 1;}if(index < 0 || index >= arrLen || index > remain || remain < 0) {return 0;}if(cache[index][remain] != 0) {return cache[index][remain];}long value = 0;value = (dfs(cache, index + 1, remain - 1, arrLen) % MOD +dfs(cache, index, remain - 1, arrLen) % MOD +dfs(cache, index - 1, remain - 1, arrLen) % MOD ) % MOD;cache[index][remain] = value;return cache[index][remain];}
}Number of Ways to Paint N × 3 Grid 思路：记忆化递归，这才是面试的时候能够表现出来的；dfs(n, a0, b0, c0, dp) 代表的物理意义是：面对第n行row，我的当前层的颜色是a0,b0,c0的情况下，我能够选择的种类有多少；然后用三个for循环，下一层如果是a, b, c 那么就有关系；a != a0, b != b0 && b != a, c != c0 && c != b; 这一层的选择种类就是： ans += dfs(n -1, a, b, c, dp); 写法：相当于，最后一层是0，0，0，从第0层开始，计算到底端，再往上走；
class Solution {private int MOD = 1000000007;public int numOfWays(int n) {if(n <= 0) return 0;int[][][][] cache = new int[n + 1][4][4][4];return dfs(0, 0, 0, 0, cache);}private int dfs(int row, int a0, int b0, int c0, int[][][][] cache) {// 递归到最底层，就是输入的a0, b0, c0三种颜色组合了；以这三个颜色往上走；if(row == cache.length - 1) {return 1;}if(cache[row][a0][b0][c0] != 0) {return cache[row][a0][b0][c0];}int[] colors = {1,2,3};int value = 0;for(int a : colors) {if(a == a0) {continue;}for(int b: colors) {if(b == b0 || b == a) {continue;}for(int c: colors) {if(c == c0 || c == b) {continue;}value = (value % MOD + dfs(row + 1, a, b, c, cache) % MOD) % MOD;}}}cache[row][a0][b0][c0] = value;return cache[row][a0][b0][c0];}
}Minimum Distance to Type a Word Using Two Fingers 思路：记忆化搜索，top down dp，两个手指move，可以写一个cost function计算两个点的cost，这个没有问题，那么问题转换成下一个move由谁来完成，cost分别是多少。top down就是最后一步，如果由左边完成，cost + dfs(左边)， 由右边完成，cost + dfs(右边）建立一个三维的dp，[leftindex][rightindex][pos in word]来标记计算过的结果；Time ( n * 27 ^ 2); Space ( n * 27 ^ 2); 27，只是为了char为null的时候，index可以包含null的情况，设置为0； 刚开始设置为null，这样两个指头走上第一char的时候，cost 会return 0；
class Solution {public int minimumDistance(String word) {if(word == null || word.length() == 0) {return 0;}int n = word.length();int[][][] dp = new int[27][27][n]; // 27，只是为了char为null的时候，index可以包含null的情况，设置为0；return dfs(word, 0, dp, null, null);// 刚开始设置为null，这样两个指头走上第一char的时候，cost 会return 0；}private int dfs(String word, int index, int[][][] dp, Character c1, Character c2) {if(index == word.length()) {return 0;}int index1 = c1 == null ? 0 : c1 - 'A' + 1;int index2 = c2 == null ? 0 : c2 - 'A' + 1;if(dp[index1][index2][index] != 0) {return dp[index1][index2][index];} char next = word.charAt(index);dp[index1][index2][index] = Math.min(cost(c1, next) + dfs(word, index+1, dp, next, c2),cost(c2, next) + dfs(word, index+1, dp, c1, next));return dp[index1][index2][index];}private int cost(Character c1, Character c2) {if(c1 == null || c2 == null) {return 0;}int len1 = c1 - 'A'; int len2 = c2 - 'A';int x1 = len1 / 6; int x2 = len2 / 6;int y1 = len1 % 6; int y2 = len2 % 6;return Math.abs(x1 - x2) + Math.abs(y1 - y2);}
}Kth Ancestor of a Tree Node 思路：直接存个parent的depth信息就可以过。估计直接height[node] < k 这个判断，省去了很多时间；因为搜索O(N + K)；findHeight用到了记忆化递归； 最优解是binary lifting，看原帖。
class TreeAncestor {private int n;private int[] parent;private int[] height;public TreeAncestor(int n, int[] parent) {this.n = n;this.parent = parent;this.height = new int[n];for(int i = 0; i < n; i++) {findHeight(i);}}private int findHeight(int node) {if(node == 0 || height[node] != 0) {return height[node];}height[node] = height[parent[node]] + 1;return height[node];}public int getKthAncestor(int node, int k) {if(height[node] < k) {return -1;}int res = node;while(k > 0) {res = parent[res];k--;}return res;}
}/*** Your TreeAncestor object will be instantiated and called as such:* TreeAncestor obj = new TreeAncestor(n, parent);* int param_1 = obj.getKthAncestor(node,k);*/Burst Balloons 区间型动态规划，可以用DFS + Cache来解决，而且比较好想。思路：f[i][j]代表：i个气球和j个气球不能被扎破的情况下，中间扎破能够得到的最大值。记住首尾先要加入一个1，然后区间型动态规划，一定是先计算小区间然后计算大区间，所以for循环用len来写，然后枚举起点，最后得到整个区间的最大值；
class Solution {public int maxCoins(int[] nums) {int n = nums.length;int[] A = new int[n + 2];// 最左边和最右边放值1；A[0] = 1; A[A.length - 1] = 1;for(int i = 1; i < A.length - 1; i++) {A[i] = nums[i - 1];}n += 2;int[][] dp = new int[n][n];// [1] A[0]....A[n - 2] [1]// 枚举length，区间型动态规划，都是从length从小到大计算的；for(int len = 2; len <= n; len++) {for(int i = 0; i + len - 1 < n; i++) {int j = i + len - 1;for(int k = i + 1; k < j; k++) {dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + A[i]* A[k]* A[j]);}}}return dp[0][n - 1];}
}思路2：这题可以用Stone Game的记忆化递归来做，score(start, end, fullNums, cache); O(N^2); top down的解法；也就是算每个一点，最后扎破，看计算出来谁最大，谁就是答案；扎破中间的气球的时候，假设左右两边全部爆掉了；也就是看最后一步；O(N^2);
class Solution {public int maxCoins(int[] nums) {if(nums == null || nums.length == 0) {return 0;}int n = nums.length;int[] A = new int[n + 2];A[0] = 1; A[A.length - 1] = 1;for(int i = 1; i < A.length -1; i++) {A[i] = nums[i - 1];}n += 2;int[][] cache = new int[n][n];return dfs(A, 0, n - 1, cache);}private int dfs(int[] A, int start, int end, int[][] cache) {if(start >= end) {return 0;}if(cache[start][end] != 0) {return cache[start][end];}int value = 0;for(int k = start + 1; k < end; k++) {value = Math.max(value, A[start] * A[k] * A[end] + dfs(A, start, k, cache) + dfs(A, k, end, cache));}cache[start][end] = value;return cache[start][end];}
}Stone Game score(A, l, r)代表面对 s[l]...s[r] 区间，我能够取得的相对的最大值，也就是我的值减去对手的值，要最大；博弈型都是相互min对方的解，max自己的解； 不用cache，会超时TLE; 加入cache, O(N^2) ，因为总共有r, l N^2个解，每个解用了cache就是O(1)，所以就是O(N^2).
class Solution {public boolean stoneGame(int[] A) {if(A == null || A.length == 0) {return false;}int n = A.length;int[][] cache = new int[n][n];for(int i = 0; i < n; i++) {Arrays.fill(cache[i], -1);}return dfs(A, 0, n - 1, cache) >= 0;}private int dfs(int[] A, int start, int end, int[][] cache) {if(start > end) {return 0;}if(cache[start][end] != -1) {return cache[start][end];}if(start == end) { // 注意相等的时候，要返回A[start];return A[start];} else {int value = Math.max(A[start] + dfs(A, start + 1, end, cache),A[end] + dfs(A, start, end - 1, cache));cache[start][end] = Math.max(cache[start][end], value);}return cache[start][end];}
}Triangle 思路1： 记忆化搜索，注意首先赋值为Integer.MAX_VALUE; 然后判断有没有访问过；
class Solution {public int minimumTotal(List<List<Integer>> A) {int n = A.size();int m = A.get(n - 1).size();int[][] cache = new int[n][m];return dfs(A, 0, 0, cache);}private int dfs(List<List<Integer>> A, int x, int y, int[][] cache) {int n = A.size();int m = A.get(n - 1).size();if(x >= n || y >= m) {return 0;}if(cache[x][y] != 0) {return cache[x][y];}cache[x][y] = Math.min(dfs(A, x + 1, y, cache), dfs(A, x + 1, y + 1, cache)) + A.get(x).get(y);return cache[x][y];}
}思路2：用标准的dp的方法来做，从下往上计算；递推公式dp[i][j] = Math.min( dp[i+1][j] , dp[i+1][j+1] ) + triangle[i][j]; 初始化最后一行，然后往上计算。这次也是beat 91.6% submission，记忆化搜索跟动态规划是等价的。使用滚动数组，优化空间，N*N的矩阵，只用最后两行，2*N的数组就可以完成，就是算完一个给另外一个，相互赋值；牛逼的方法是，所有的row坐标 % 2， 滚动数组，从row开始循环，就是row % 2，从col开始循环就是col % 2， 另外initial的时候也要% 2；
class Solution {public int minimumTotal(List<List<Integer>> triangle) {int m = triangle.size();int n = triangle.get(m - 1).size();int[][] dp = new int[m][n];// initial last row;for(int j = 0; j < n; j++) {dp[m - 1][j] = triangle.get(m - 1).get(j);}// calculate from bottom to top;for(int i = m - 2; i >= 0; i--) {// 注意这里不能用n，只能每行每行的算size，因为有短小的，会有NPE；for(int j = 0; j < triangle.get(i).size(); j++) {dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);}}return dp[0][0];}
}滚动数组，Space 优化到O(m);
class Solution {public int minimumTotal(List<List<Integer>> triangle) {int m = triangle.size();int n = triangle.get(m - 1).size();int[][] dp = new int[2][n];// initial last row;for(int j = 0; j < n; j++) {dp[(m - 1) % 2][j] = triangle.get(m - 1).get(j);}// calculate from bottom to top;for(int i = m - 2; i >= 0; i--) {// 注意这里不能用n，只能每行每行的算size，因为有短小的，会有NPE；for(int j = 0; j < triangle.get(i).size(); j++) {dp[i % 2][j] = triangle.get(i).get(j) + Math.min(dp[(i + 1) % 2][j], dp[(i + 1) % 2][j + 1]);}}return dp[0][0];}
}Number of Dice Rolls With Target Sum 思路：dp[i][j] 表示 用了i个筛子，能够得到和为j的 possible ways是多少；
class Solution {private int MOD = 1000000007;public int numRollsToTarget(int d, int f, int target) {if(d <= 0 || f <= 0 || target <= 0) {return 0;}int[][] dp = new int[d + 1][target + 1];for(int i = 0; i <= d; i++) {for(int j = 0; j <= target; j++) {if(i == 0 && j == 0) {dp[i][j] = 1;} else {for(int k = 1; k <= f; k++) {if(i - 1 >= 0 && j - k >= 0)dp[i][j] = (dp[i][j] % MOD + dp[i - 1][j - k] % MOD) % MOD;}}}}return dp[d][target];}
}DFS + Memo, 有两个变化的维度，一个是d，一个是target；[1, f];
class Solution {private int MOD = 1000000007;public int numRollsToTarget(int d, int f, int target) {if(d <= 0 || f <= 0 || target <= 0) {return 0;}Integer[][] cache = new Integer[d + 1][target + 1];return dfs(d, f, target, cache);}private int dfs(int d, int f, int target, Integer[][] cache) {if(d < 0 || target < 0) {return 0;}if(d == 0) {return target == 0 ? 1 : 0;}if(cache[d][target] != null) {return cache[d][target];}int value = 0;for(int k = 1; k <= f; k++) {value = (value % MOD + dfs(d - 1, f, target - k, cache) % MOD) % MOD;}cache[d][target] = value;return cache[d][target]; }
}Maximum Vacation Days 思路：DFS + Memo： 注意当前一层week，我可以take flight，去任何一个大的value，所以value 加的是days[j][week];只要curcity == j || flights[curcity][j] == 1，那么就可以计算下一层；
class Solution {public int maxVacationDays(int[][] flights, int[][] days) {if(flights == null || flights.length == 0 || days == null || days.length == 0) {return 0;}int n = days.length; // city;int m = days[0].length; // week;Integer[][] cache = new Integer[n][m];return dfs(flights, days, 0, 0, cache);}private int dfs(int[][] flights, int[][] days, int curcity, int week, Integer[][] cache) {if(week == days[0].length) {return 0; }if(cache[curcity][week] != null) {return cache[curcity][week];}int value = 0;// loop all the city;for(int j = 0; j < days.length; j++) {if(curcity == j || flights[curcity][j] == 1) {// 当前week可以达到的最大 + 下一层的最大；value = Math.max(value, days[j][week] + dfs(flights, days, j, week + 1, cache));}}cache[curcity][week] = value;return cache[curcity][week];}
}Form Largest Integer With Digits That Add up to Target 思路：这题暴力解，就是backtracking，但是这题这样想：我选择一个数之后，target减少，那么给定target找最大的数，又是一个子问题，那么给定target，就有最优解，那么这可以用dp来cache住最优解，那么就是我选择了一个数d + dfs(subproblem)，我每次从9往0走，greedy的走，这样只要result的string的长度在增加，那么就是最优的，因为前面都是最优的解，我cache住了，那么从后往前走，得到的最长的string，就是最优的解；huahua有个思维导图，很清晰，贴过来，就是怎么表示subproblem；Time: O(target * target);
class Solution {public String largestNumber(int[] cost, int target) {String[] dp = new String[target + 1];return dfs(cost, target, dp);}private String dfs(int[] cost, int target, String[] dp) {if(target < 0) {return "0";}if(target == 0) {return "";}if(dp[target] != null) {return dp[target];}String res = "0";for(int d = 9; d >= 1; d--) {String cur = dfs(cost, target - cost[d - 1], dp);if(cur.equals("0")) {continue;}cur = d + cur;if(res.equals("0") || cur.length() > res.length()) {res = cur;}}dp[target] = res;return dp[target];}
}思路2：这题可以buttom up写；计算顺序就是：t从1到target，然后d从1到9，一个个试探，生成最优解；
class Solution {public String largestNumber(int[] cost, int target) {String[] dp = new String[target + 1];Arrays.fill(dp, "0");dp[0] = "";for(int t = 1; t <= target; t++) {for(int d = 1; d <= 9; d++) {int s = t - cost[d - 1];if(s < 0 || dp[s].equals("0") || dp[s].length() + 1 < dp[t].length()) {continue;}dp[t] = d + dp[s];}}return dp[target];}
}这篇关于记忆化搜索总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
