告别动态规划，连刷 40 道题，我总结了这些套路，看不懂你打我 - 知乎
北美算法面试的题目分类，按类型和规律刷题
一维dp
矩阵型DP
方法一：自定向下 + memo
class Solution {
Map<Integer,Integer> m = new HashMap<>();
int helper(int[] nums, int right){
if(m.containsKey(right)){
return m.get(right);
}
if(right == 0){
m.put(right, nums[0]);
return nums[0];
}
else if(right == 1){
int i = Math.max(nums[0], nums[1]);
m.put(right, i);
return i;
}
int i = Math.max(helper(nums, right - 2) + nums[right], helper(nums, right-1));
m.put(right, i);
return i;
}
public int rob(int[] nums) {
if(nums.length == 0) return 0;
return helper(nums, nums.length - 1);
}
}方法二：自底向上 + memo
class Solution {
public int rob(int[] nums) {
if(nums.length == 0) return 0;
int[] memo = new int[nums.length];
for(int i=0; i<nums.length; i++){
if(i == 0 ) memo[i] = nums[i];
else if(i == 1){
memo[i] = Math.max(nums[0], nums[1]);
}
else{
memo[i] = Math.max(memo[i-1], memo[i-2] + nums[i]);
}
}
return memo[nums.length - 1];
}
}方法三：自底向上 + memo optimised
class Solution {
public int rob(int[] nums) {
if(nums.length == 0) return 0;
if(nums.length == 1) return nums[0];
int n_1 = nums[0], n_2 = 0;
for(int i=1; i<nums.length; i++){
int t = Math.max(n_1, n_2 + nums[i]);
n_2 = n_1; n_1 = t;
}
return n_1;
}
}方法：同上
class Solution {
public int rob(int[] nums) {
if(nums.length == 0) return 0;
if(nums.length == 1) return nums[0];
if(nums.length == 2) return Math.max(nums[0], nums[1]);
int x = 0;
// 1. drop the last num
int n2 = nums[0], n1 = Math.max(nums[0], nums[1]);
for(int i = 2; i < nums.length -1; i ++){
int t = Math.max(n2 + nums[i], n1);
n2 = n1;
n1 = t;
}
x = n1;
n2 = 0;
n1 = nums[1];
for(int i = 2; i < nums.length; i ++){
int t = Math.max(n2 + nums[i], n1);
n2 = n1;
n1 = t;
}
return Math.max(x, n1);
}
}方法一： 自顶向下 + memo
这种方式写起来容易出错，效率也比较低
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Map<TreeNode, Integer> m = new HashMap<TreeNode, Integer>();
Map<TreeNode, Integer> m2 = new HashMap<TreeNode, Integer>();
int helper(TreeNode t, boolean parentUsed){
if(t == null) return 0;
if(parentUsed){
if(m.containsKey(t)){
return m.get(t);
}
int x = helper(t.left, false) + helper(t.right, false);
m.put(t, x);
return x;
}
else{
if(m2.containsKey(t)){
return m2.get(t);
}
int notUse = helper(t.left, false) + helper(t.right, false);
int use = t.val + helper(t.left, true) + helper(t.right, true);
int x = Math.max(use, notUse);
m2.put(t, x);
return x;
}
}
public int rob(TreeNode root) {
if(root == null) return 0;
return Math.max(root.val +
helper(root.left, true) + helper(root.right,true),
helper(root.left, false) + helper(root.right, false));
}
}方法二：自顶向下 + memo
虽然也是自顶向下，下面的方法就简洁很多；特别注意标important那行容易出错
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int[] helper(TreeNode t){
int[] re = new int[2];
if(null == t){
re[0] = 0;
re[1] = 0;
return re;
}
int[] left = helper(t.left);
int[] right = helper(t.right);
re[0] = t.val + left[1] + right[1];
re[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // important
return re;
}
public int rob(TreeNode root) {
if(root == null) return 0;
int[] re = helper(root);
return Math.max(re[0], re[1]);
}
}方法一：自顶向下
递归法,time limited
class Solution {
int helper(int[][] g, int x, int y){
int top = 0, left = 0;
if(g[x][y] == 1) return 0;
if(x == 0 && y == 0) return 1;
if(x > 0){
top = helper(g, x - 1, y);
}
if(y > 0){
left = helper(g, x, y - 1);
}
return top + left;
}
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
return helper(obstacleGrid, obstacleGrid.length - 1, obstacleGrid[0].length -1);
}
}方法一：自顶向下
递归法 + memo ac
class Solution {
Map<Long, Integer> m = new HashMap<>();
int helper(int[][] g, int x, int y){
int top = 0, left = 0;
if(g[x][y] == 1) return 0;
if(x == 0 && y == 0) return 1;
long key = ((long)x) << 32 | y; // long key = x << 32 | y; 错误
if(m.containsKey(key)) return m.get(key);
if(x > 0){
top = helper(g, x - 1, y);
}
if(y > 0){
left = helper(g, x, y - 1);
}
m.put(key, top + left);
return top + left;
}
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
return helper(obstacleGrid, obstacleGrid.length - 1, obstacleGrid[0].length -1);
}
}方法三：自底向上
递推 + memo
这里用了二维memo，其实状态转移中，当前step只与上一step有关系，只用一维memo就可以了。
class Solution {
public int uniquePathsWithObstacles(int[][] g) {
if(g.length == 0) return 0;
int[][] ps = new int[g.length][g[0].length];
boolean obstacle = false;
for(int i = 0; i < g.length; i ++){
if(g[i][0] == 1){
obstacle = true;
}
ps[i][0] = obstacle ? 0 : 1;
}
obstacle = false;
for(int i = 0; i < g[0].length; i ++){
if(g[0][i] == 1){
obstacle = true;
}
ps[0][i] = obstacle ? 0 : 1;
}
for(int i = 1; i < g.length; i++){
for(int j = 1; j < g[0].length; j++){
if(g[i][j] == 1){
ps[i][j] = 0;
}
else{
ps[i][j] = ps[i-1][j] + ps[i][j-1];
}
}
}
return ps[g.length-1][g[0].length-1];
}
}方法一：自底向上 + 二维memo
class Solution {
public int minPathSum(int[][] g) {
if (g.length == 0) return 0;
int[][] sum = new int[g.length][g[0].length];
sum[0][0] = g[0][0];
for(int i = 1; i < g.length; i++){
sum[i][0] = g[i][0] + sum[i-1][0];
}
for(int i = 1; i < g[0].length; i++){
sum[0][i] = g[0][i] + sum[0][i-1];
}
for(int i = 1; i < g.length; i ++){
for(int j = 1; j < g[0].length; j++){
sum[i][j] = g[i][j] + Math.min(sum[i-1][j], sum[i][j-1]);
}
}
return sum[g.length-1][g[0].length-1];
}
}方法二：自底向上 + 一维memo
class Solution {
public int minPathSum(int[][] g) {
if (g.length == 0) return 0;
int[] sum = new int[g[0].length];
sum[0] = g[0][0];
for(int i = 1; i < g[0].length; i++){
sum[i] = g[0][i] + sum[i-1];
}
for(int i = 1; i < g.length; i ++){
sum[0] = sum[0] + g[i][0];
for(int j = 1; j < g[0].length; j++){
sum[j] = g[i][j] + Math.min(sum[j], sum[j-1]);
}
}
return sum[g[0].length-1];
}
}解法一： 自顶向下，递归 + no memo, time limit exceed
这道题真有点不太好想
class Solution {
int helper(char[] str, int right){
int sum1 = 0, sum2 = 0;
if(right < 0) return 1;
if(right == 0){
return (str[right] != '0') ? 1 : 0;
}
if(str[right] != '0'){
sum1 = helper(str, right-1);
}
if(str[right-1] != '0'){
Integer x = Integer.valueOf(new String(str, right - 1, 2));
if(x >= 1 && x <= 26){
sum2 = helper(str, right-2);
}
}
return sum1 + sum2;
}
public int numDecodings(String s) {
return helper(s.toCharArray(), s.length() - 1);
}
}解法二： 自顶向下，递归 + memo
class Solution {
Map<Integer, Integer> m = new HashMap<>();
int helper(char[] str, int right){
int sum1 = 0, sum2 = 0;
if(m.containsKey(right)){
return m.get(right);
}
if(right < 0) return 1;
if(right == 0){
return (str[right] != '0') ? 1 : 0;
}
if(str[right] != '0'){
sum1 = helper(str, right-1);
}
if(str[right-1] != '0'){
Integer x = Integer.valueOf(new String(str, right - 1, 2));
if(x >= 1 && x <= 26){
sum2 = helper(str, right-2);
}
}
m.put(right, sum1+sum2);
return sum1 + sum2;
}
public int numDecodings(String s) {
return helper(s.toCharArray(), s.length() - 1);
}
}方法三：自底向上 + 加 O(n) memo
class Solution {
public int numDecodings(String s) {
if(s.length() == 0 || s.charAt(0) == '0') return 0;
int[] memo = new int[s.length() + 1];
memo[0] = 1; memo[1] = 1;
char[] str = s.toCharArray();
for(int i=1; i<s.length(); i++){
int t1 = 0, t2 = 0;
if(str[i] != '0'){
t1 = memo[i];
}
if(str[i-1] != '0'){
Integer x = Integer.valueOf(new String(str, i-1, 2));
if(x >= 10 && x <= 26){
t2 = memo[i-1];
}
}
memo[i+1] = t1 + t2;
}
return memo[s.length()];
}
}方法一 ： 自定向下
递归 + memo
问题拆分、状态、状态转移方程、初始值，一个都不能少
class Solution {
Map<Long, Integer> m = new HashMap<>();
int helper(List<List<Integer>> tri, int row, int col){
long key = (long)row << 32 | col;
if(m.containsKey(key)){
return m.get(key);
}
if ( row == 0 && col == 0 ){ //不能忽略此逻辑
return tri.get(0).get(0);
}
int left = Integer.MAX_VALUE;
int top = Integer.MAX_VALUE;
if(row > 0){
if(col < tri.get(row).size() - 1){
top = helper(tri, row - 1, col);
}
if(col > 0){
left = helper(tri, row - 1, col - 1);
}
}
int val = Math.min(top, left) + tri.get(row).get(col);
m.put(key, val);
return val;
}
public int minimumTotal(List<List<Integer>> tri) {
if(tri.size() == 0) return 0;
int sum = Integer.MAX_VALUE;
for(int j = 0; j < tri.get(tri.size()-1).size(); j++){
sum = Math.min(sum, helper(tri, tri.size()-1, j));
}
return sum;
}
}方法二 ： 自底向上
递推 + memo，下面的方法还可以进一步优化
class Solution {
public int minimumTotal(List<List<Integer>> tri) {
if(tri.size() == 0) return 0;
int[] memo = new int[tri.get(tri.size()-1).size()];
memo[0] = tri.get(0).get(0);
for(int i = 1; i < tri.size(); i ++){
for(int j = tri.get(i).size() -1; j >= 0 ; j--){
if(j == 0){
memo[j] = memo[j] + tri.get(i).get(j);
}
else if(j == tri.get(i).size() - 1){
memo[j] = memo[j-1] + tri.get(i).get(j);
}
else{
memo[j] = Math.min(memo[j-1], memo[j]) + tri.get(i).get(j);
}
}
}
int sum = Integer.MAX_VALUE;
for(int i=0; i<memo.length; i++){
sum = Math.min(sum, memo[i]);
}
return sum;
}
}方法一 ： 自顶向下
递归 + memo
class Solution {
Map<Integer, Boolean> m = new HashMap<>();
boolean helper(char[] str, int right, Set<String> dict){
if(right >= str.length){
return true;
}
if(m.containsKey(right)){
return m.get(right);
}
for(int j = 1; j < str.length - right + 1; j++){
if(dict.contains(new String(str, right, j))){
if(helper(str, right + j, dict)){
return true;
}
}
}
m.put(right, false);
return false;
}
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>();
for(String r : wordDict){
dict.add(r);
}
return helper(s.toCharArray(), 0, dict);
}
}方法二：自底向上
递推 + memo
（ps：这道题并不像经典dp，它当前状态不仅依赖于上阶段的状态，而是依赖于过去所有阶段的状态，看看grandyang的解说）
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>();
int maxi = 0;
for(String r : wordDict){
dict.add(r);
maxi = Math.max(maxi, r.length());
}
char[] arr = s.toCharArray();
boolean[] can = new boolean[s.length() + 1];
can[0] = true;
for(int i = 0; i < s.length(); i++){
boolean c = false;
for(int j = i; j >= 0 && j >= (i - maxi); j--){ // j >= (i - maxi)是优化部分
if(can[j] && dict.contains(new String(arr, j, i+1 - j))){
c = true;break;
}
}
can[i+1] = c;
}
return can[s.length()];
}
}原文：https://www.cnblogs.com/holidays/p/leetcode_note.html