When to use: 之后的结果对前面没有影响，并且存在关系 F(n)=f(F(k<n)). 解决dp问题关键是找到推进公式
问题格式： HOW MANY?? MAXMUM/MINMUM?? TURE/FALSE?? Longest/Largest??
i) 公式只用前面一个element: counting bits
ii) 公式用前面几个elements: House Robber I, II (Similar: Delete and Earn) / Sum可重复排列 Combination Sum IV / Coin Path / 4 Keys Keyboard (Similar: Integer Break) / Decode Ways II / Find the Derangement of An Array
iii) 扫描所有K次: Sum可重复组合Coin Change 2 (Similar: Coin Change利用sort优化)/ Sum不重复: 引入temp_dp[n]防止重复计算，在element只能正数时，可以从后往前扫避免重复计算 Partition Equal Subset Sum (Similar: Target Sum, Number of Dice Rolls With Target Sum) / Last Stone Weight II
iv) 公式用前面所有elements: Number of Longest Increasing Subsequence(引入新变量，每个位置还记录最长subsequence的长度) / Longest Arithmetic Sequence (引入新变量，每个位置还记录到前面所有位置的差值)/ Partition每个元素往前看，重新分区： Largest Sum of Averages (Similar: Filling Bookcase Shelves, Partition Array for Maximum Sum, Palindrome Partitioning II) / 组合Toss Strange Coins / Unique Binary Search / Perfect Squares / Word break / 2 Keys Keyboard / Largest Divisible Subset
Template
小技巧，通常内存可以2D压缩为1D，如果公式是k[i][j]=k[i-1][j-1]+k[i-1][j]。可以直接存一个vector，计算时从最后算，避免覆盖
i) 公式递进: Match两个list/string Edit Distance (Similar: Minimum ASCII Delete Sum for Two Strings, Delete Operation for Two Strings, Regular expression, Wildcard matching, Interleaving String, Maximum Length of Repeated Subarray, Shortest Common Supersequence(get path), Longest Palindromic Subsequence(reverse string产生新string), Longest Repeating Substring(复制string,只看上三角), Distinct Subsequences, Minimum Window Subsequence, Make Array Strictly Increasing) / Dungeon Game / Paint House I, II / Bomb Enemy / Maximal Square (Similar: Largest 1-Bordered Square) / Uncrossed Lines / Longest String Chain
ii) 2D整体到下一步: Knight Dialer / Knight Probability in Chessboard / Out of Boundary Paths /
iii) 1D扩为2D, state是新的degree, 内存可2D压缩为1D: Paint Fence / Minimum Swaps To Make Sequences Increasing / Max Consecutive Ones II / Domino and Trimino Tiling / Odd Even Jump / Best Time to Buy and Sell Stock III, IV, with Cooldown / Maximum Sum Circular Subarray
iv) 对角线推进: Add Parentheses / Burst Bolloons / Stone Game
Word Break II / Race Car / Stone Game II
Smallest Sufficient Team (Similar: Stickers to Spell Word / Campus Bikes II)
Template 1
Binary Search / Guess Number Higher or Lower
Template 2
i) mid>() return left-1; 找到的left>target; left-1<=target
Sqrt / First Bad Version / Arranging Coins / Single Element in a Sorted Array
ii) mid>=() return left; 找到的left>=target; left-1<target
H-Index II / Koko eating bananas / Capacity To Ship Packages Within D Days (Similar: Split Array Largest Sum)/ Kth Smallest Element in a sorted Matrix / Path With Maximum Minimum Value / Find K Closest Elements / Find Minimum in Rotated Sorted ArrayI, II
iii) 夹逼求值 Minimize Max Distance to Gas Station / Median of Two Sorted Arrays
Max Sum of Rectangle No Larger Than K / Longest Increasing Subsequence (Similar: Russian Doll Envolopes) / Odd Even Jump / Number of Matching Subsequences / Missing Element in Sorted Array / Online Election / Snapshot Array
Two City Scheduling / Minimize Rounding Error to Meet Target
every try must be correct if backtrack not used
i) grid Template 1
Longest Increasing Path in a Matrix / Making A Large Island / Coloring A Border / Regions Cut By Slashes / Candy Crush
ii) vector Coin Change / Brace Expansion
iii) Graph Graph Valid Tree / Possible Bipartition
i) 对vector上的元素每个都试一下, O(2^N) Template 1
Combination Sum I, II, III / (Similar: Shopping Offers) / Expression Add Operators / Subsets I, II / Combinations / Binary Watch / Palindrome Partitioning / Letter Combinations of a Phone Number / Generate Parentheses / Increasing Subsequences
ii) 2D try different pos: N Queues I, II / Sudoku Solver / Android Unlock Patterns / Robot Room Cleaner
iii) O(N!): Permutations I, II (Similar: Number of Squareful Arrays)
iv) tree: Binary Tree Paths / Path Sum II
Template 2
Word search / Reconstruct Itinerary / Word Pattern II
Partition to K equal Sum / Pyramid Transition Matrix
i) Grid: Template
Walls and Gates / 01 Matrix / Sliding Puzzle
ii) Vector: Snakes and Ladders /
iii) Graph: Is Graph Bipartite? (Similar: Possible Bipartition) / Cheapest Flights Within K Stops / Bus Routes / All Nodes Distance K in Binary Tree / Maximum Width of Binary Tree
/ Word Ladder II
When to use: 整体和局部都有相同的性质，利用这些性质。最直接的应用就是tree, palindrome string
i) Number: Permutation Sequence
ii) String: Scramble String / Integer to English Words
Jump Game I, II / Gas Station / Remove K Digits / Video Stitching / Course Schedule III / Coin Change / Distant Barcodes / Delete Columns to Make Sorted II / Flower Planting With No Adjacent / Non-overlapping Intervals (Similar: Minimum Number of Arrows to Burst Balloons) / Maximum Nesting Depth of Two Valid Parentheses Strings / Minimum Cost Tree From Leaf Values / Container With Most Water / Huffman Coding: Minimum Time to Build Blocks
Template
Redundant Connection I, II / Friend Circles / Satisfiability of Equality Equations / Sentence Similarity II / Evaluate Division / Most Stones Removed with Same Row or Column /Largest Component Size by Common Factor / Accounts Merge / Lexicographically Smallest Equivalent String / Connecting Cities With Minimum Cost
Template
i) position Grumpy Bookstore Owner / Max Consecutive Ones III / Count of Range Sum / Moving Stones Until Consecutive II / Find K-Length Substrings With No Repeated Characters
ii) unordered_map Longest Substring Without Repeating Characters (Similar: Longest Substring with At Most K Distinct, Minimum Window Substring, Substring with Concatenation of All Words / Longest Substring with At Least K Repeating Characters)
Camelcase Matching / Expressive Words / Interval List Intersections / Shortest Way to Form String / String Compression / Partition Array Into Three Parts With Equal Sum / Read N Characters Given Read4 I, II / Find K Closest Elements / Merge Sorted Array / Populating Next Right Pointers in Each Node
Find the Celebrity / Max Chunks To Make Sorted I, II / Diagonal Traverse / Flatten 2D Vector / Pancake Sorting / 数据小，避免map降低复杂度：Friends Of Appropriate Ages
i) find: Repeated Substring Pattern / Index Pairs of a String / Corporate Flight Bookings reverse: Reverse Words in a String
ii) other: Greatest Common Divisor of Strings / Multiply Strings
iii) stringstream: Serialize and Deserialize Binary Tree, Serialize and Deserialize N-ary Tree ,Encode and Decode Strings / getline Goat Latin
i) Merge list: Merge Two Sorted Lists / Merge k Sorted Lists / AddTwoNumbers
ii) reverse list: Palindrome Linked List / Reorder List
i) Recursive: Balanced Binary Tree / Longest Univalue Path (Similar: Binary Tree Maximum Path Sum / Distribute Coins in Binary Tree) / Lowest Common Ancestor of a Binary Tree (Lowest Common Ancestor of Deepest Leaves) / All Possible Full Binary Trees / Serialize and Deserialize Binary Tree / Insufficient Nodes in Root to Leaf Paths
ii) Recursive+dfs: 特点：要找的result不在root上，要对每个结点recursive
Subtree of Another Tree / Path Sum III / Delete Nodes And Return Forest
iii) Iterative traversal: Binary Tree Inorder Traversal (Similar: Binary Tree Preorder, Binary Tree Postorder, Binary Tree Level Order II, Binary Tree Vertical Order Traversal, Vertical Order Traversal of a Binary Tree, N-ary Tree Postorder, N-ary Tree Level Order) / Leaf-Similar Trees / Recover a Tree From Preorder Traversal (Similar: Construct Binary Tree from Preorder and Postorder Traversal) / Binary Search Tree Iterator
iv) DP: House Robber III / Binary Tree Cameras
i) Find number: Insert into a Binary Search Tree / Delete Node in a BST / Inorder Successor in BST
ii) Traversal: Minimum Distance Between BST Nodes (Similar: Recover Binary Search Tree / Find Mode in BST, Validate BST, Kth Smallest Element in a BST, Increasing Order Search Tree)
iii) Range: Lowest Common Ancestor of BST / Validate BST / Convert BST to Sorted Doubly Linked List / Construct Binary Search Tree from Preorder Traversal
Palindrome Pairs / Implement Trie (Prefix Tree) / Stream of Characters / Prefix and Suffix Search / Add and Search Word - Data structure / Repalce Words / string变set压缩tree:Number of Valid Words for Each Puzzle / tire压缩string list+backtrack tire:Word Search II
i) Range Sum Query - Mutable
ii) Merge intervals: Key: start+end Value: sth Corporate Flight Bookings (Similar: Add Bold Tag in String) / Key: start, Value: end Range Module / interval+multiset The Skyline Problem
i) Stack Maximum Width Ramp / Remove All Adjacent Duplicates In String / Basic Calculator I, II, III
ii) Mono Stack Online Stock Span / Daily Temperatures / Sum of Subarray Minimums / Largest Rectangle in Histogram (Similar: Maximal Rectangle)/ Next Greater Element II / Number of Valid Subarrays
iii) Queue Design Hit Counter
iv) Priority_queue Huffman coding: Minimum Time to Build Blocks (Similar: Last Stone Weight) / Minimum Cost to Hire K Workers.h / Rearrange String k Distance Apart
v) Deque(之前出现的大于/小于的之后一定用不到，这样两头都可以加入) Sliding Window Max / Shortest Subarray with Sum at Least K
i) Map Max Stack / Time Based Key-Value Store / Analyze User Website Visit Pattern
ii) Unordered_map 压缩空间: Encode and Decode TinyURL, Sparse Matrix Multiplication, Max Points on a Line / map找到相同性质的,m[性质]++: Flip Columns For Maximum Number of Equal Rows, Subarray Sums Divisible by K / m[性质]=index: Contiguous Array, Fraction to Recurring Decimal / O(N) * 2: Longest Consecutive Sequence
iii) Set Rectangle Area II
iv) Unordred_set Longest Word in Dictionary / Longest Well-Performing Interval
v) multiset 相同时insert到后面 Find Median from Data Stream / erase with find The Skyline Problem
Template use priority queue in BFS rather than queue to integrate cost
Network Delay Time (Similar: Cheapest Flights Within K Stops) / Connecting Cities With Minimum Cost
indegree is similar to level in BFS: Course Schedule I, II / Sequence Reconstruction / Alien Dictionary / Find Eventual Safe States / Find the Town Judge / Minimum Height Trees
Count one Counting Bits (Similar: Power of Four, Power of Two) / Reverse Bits/ Sum of Two Integers / Divide Two Integers / Total Hamming Distance / ^ cancel digits Single Number I, II, III (Similar: Missing Number, Find the Difference) / Convert to Base -2 / Adding Two Negabinary Numbers
Bitset Binary String With Substrings Representing 1 To N
https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently
Two Sum (Similar: Subarray Sum Equals K, Split Array with Equal Sum ) / 3Sum / Number of Submatrices That Sum to Target / Count of Range Sum / Prefix sum: Can Make Palindrome from Substring
i) merge sort Reverse Pair / Count of Range Sum / Count of Smaller Numbers After Self / Merge k Sorted Lists
ii) Campus Bikes
Number of Submatrices That Sum to Target / Range Sum Query 2D - Mutable, - Immutable /
Rectangle Area (Similar: Rectangle Overlap)
Valid Parenthesis String (Similar: Minimum Add to Make Parentheses Valid, Remove Invalid Parentheses) / 开始新的一行处理(, 关掉一行当遇到)时: Reverse Substrings Between Each Pair of Parentheses (Similar: Number of Atoms)