DP is a hard topic, but many problems have similar patterns. Once you get familiar with these patterns, these problems will be easy to approach. In this post, I will cover some relatively easier and apparent patterns using some example codes and similar practice questions. I hope it will be helpful to you.
1. Array or matrix traversal
These includes a 1d array or more 2d matrix, or two arrays or strings, they are generally not hard dp problem since the recurrence relation is not hard to find.
-
two directions traversal
one direction to get the dp value for previous, then try another direction to satisfy the other direction.-
135 Candy 32.4% Hard
-
542 01 Matrix 40.3% Medium
-
1162 As Far from Land as Possible 44.3% Medium
-
-
using previous row and previous col to get current dp value
most these problem only depends on previous row and column.- 799 Champagne Tower 43.8% Medium
- 174 Dungeon Game 32.9% Hard
- 120 Triangle 45.0% Medium
min path sum from top to bottom. (try from bottom to top) - 64 Minimum Path Sum 55.4% Medium
- 63 Unique Paths II 35.0% Medium (with obstacles)
- 62 Unique Paths 55.1% Medium
this is also a math permutation of m D and n R. - 931 Minimum Falling Path Sum 63.1% Medium
- 1289 Minimum Falling Path Sum II 61.8% Hard ***
adjacent row cannot choose the same col, col does not need to be adjacent.
so with greedy approach: always choose the min or 2nd min in each row. - 1594 Maximum Non Negative Product in a Matrix 31.9% Medium
similar to 1d max subarray product. need keep both min and max.
-
find square or rectangle in matrix.
generally is more tricky. these problems are all ending with (i,j) problems, i.e using current element A[i,j] as the ending element.-
562 Longest Line of Consecutive One in Matrix 46.1% Medium
horizontal, vertical, diagonal, anti-diagonal.
same: updating the 4 variables ending with (i,j). -
221 Maximal Square 38.1% Medium ***
dp[i,j] represent the max square size ending at (i,j).
dp[i,j]=min(dp[i-1,j-1],dp[i-1,j],dp[i,j-1]+1 -
1277 Count Square Submatrices with All Ones 73.0% Medium
-
1292 Maximum Side Length of a Square with Sum Less than or Equal to Threshold 49.9% ***
prefix sum, and then loop to get all submatrix sum ending with (i,j) -
750 Number Of Corner Rectangles 66.6% Medium ***
brutal force will be O(M^2N^2)
to reduce one loop. we count the two rows: number of cols with same 1, and then number of rect = c*(c-1)/2
O(N^2M). This is by changing the loop order. -
1504 Count Submatrices With All Ones 61.5% Medium ***
similarly we only store left 1 length, and then count each row from 0 to i with rect ending with (i,j).
-
-
2d but doing two 1d directions
- 764 Largest Plus Sign 46.1% Medium
- 1139 Largest 1-Bordered Square 48.1% Medium ***
-
two strings or arrays.
- 97 Interleaving String 32.2% Hard
- 1458 Max Dot Product of Two Subsequences 42.5% Hard
similar to LCS. -
- Longest Palindromic Substring
-
- Edit Distance
-
- Delete operation for two strings
-
- Minimum ASCII delete sum for two strings
- 10 Regular Expression Matching 27.1% Hard
- 44 Wildcard Matching 25.1% Hard
2. longest common subsequence (LCS)
-
two array or two strings and get the longest common subsequence
-
get the length or all the LCS.
-
longest palindrome problems can be treated as LCS between string and reversed string.
-
can also be consider as a 2d matrix traversal.
-
dp[i,j] represent the longest common subsequence length for s1 with length=i and s2 with length=j.
-
important: develop intuition to convert to equivalent LCS problem.
-
- longest common subsequence
- 516 Longest Palindromic Subsequence 54.4% Medium
-
- Uncrossed lines
- 583 Delete Operation for Two Strings 49.4% Medium
delete from one string to another string, equiv LCS - 1216 Valid Palindrome III 48.8% Hard
if we can remove at most k chars to make it palindrome. equiv LCS between s and reversed s. - 1312 Minimum Insertion Steps to Make a String Palindrome 58.8% Hard
- 1092 Shortest Common Supersequence 52.5% Hard ***
find the LCS: the string.
-
3. Longest increasing subsequence (LIS)
-
generally only one array or string is involved.
-
O(nlogn) approaches is applied when better complexity is needed.
-
all ending with problem (thus we tried each element as candidates). ie. we loop each element as the ending element and connect with previous elements satisfying the condition.
-
300 Longest Increasing Subsequence 43.0% Medium
-
673 Number of Longest Increasing Subsequence 38.2% Medium
LIS and count number of ways to reach LIS. two dp problems. -
368 Largest Divisible Subset 38.1% Medium ***
sort and check previous if num[i]%num[j]==0
to get the combination add a prev array to store previous position. -
474 Ones and Zeroes 43.3% Medium
choose it dp[i,j]=max(dp[i,j],dp[i-m0,j-n1]+1) -
354 Russian Doll Envelopes 35.8% Hard
2d compare. -
646 Maximum Length of Pair Chain 52.4% Medium
-
1048 Longest String Chain 55.2% Medium
-
960 Delete Columns to Make Sorted III 54.0% Hard
-
955 Delete Columns to Make Sorted II 33.4% Medium
-
944 Delete Columns to Make Sorted 70.9% Easy
-
1027 Longest Arithmetic Subsequence 50.4% Medium
2d dp with LIS. -
- Min operation to make a subsequence
-
1218 Longest Arithmetic Subsequence of Given Difference 45.9% Medium
-
1187 Make Array Strictly Increasing 41.5% Hard
-
1626 Best Team With No Conflicts 36.7% Medium
-
- Minimum Number of Removals to Make Mountain Array
-
- Maximum Height by stacking cuboids
-
1239. Maximum Length of a Concatenated String with Unique Characters
brute force: try all combinations of the strings in the array
LIS: sort the strings from longest to shortest (greedy so that we use longer one first). dp[i] stores the longest string ending with A[i] (using bitset to simplify the AND/OR/XOR bit manipulations), then we check all previous dp[j] and get the longest length.
-
int maxLength(vector<string>& arr) {
int n=arr.size();
sort(begin(arr),end(arr),[](string& a,string& b){
return a.size()>b.size();
});
vector<bitset<26>> dp(n);
int ans=0;
for(int i=0;i<n;i++){
bitset<26> bs;
for(char c: arr[i]) bs[c-'a']=1;
if(bs.count()<arr[i].size()) continue; //this one is invalid
bitset<26> mxbs=bs;
dp[i]=bs;
for(int j=0;j<i;j++){
bitset<26> bs0=dp[i]&dp[j];
if(bs0.count()==0){
bs0=dp[i]|dp[j];
if(bs0.count()>mxbs.count()) mxbs=bs0;
}
}
dp[i]=mxbs;
ans=max(ans,(int)dp[i].count());
}
return ans;
}4. Array partitioning (connect or start a new group)
this is a very typical dp pattern. Typical pattern is to partition the array into several parts and to reach global optimal results. We try each element to attach to previous partition or start a new partion and evaluate the optimal results.
- 309 Best Time to Buy and Sell Stock with Cooldown 47.8% Medium
as many as transactions. ->partition to any parts.
- 188 Best Time to Buy and Sell Stock IV 28.8% Hard
at most k transactions.
- 123 Best Time to Buy and Sell Stock III 39.3% Hard
at most 2 transactions.
- 122 Best Time to Buy and Sell Stock II 57.9% Easy
as many transaction as you want.
- 121 Best Time to Buy and Sell Stock 51.1% Easy
at most one transaction (this is the base for all stock problem)
- 714 Best Time to Buy and Sell Stock with Transaction Fee 55.4% Medium
all based on max(current - lmin)
- 472 Concatenated Words 44.9% Hard
dp[i] represent true or fase to be able to cut here to deocompose it into dictionary words.
- 140 Word Break II 33.7% Hard
- 139 Word Break 41.0% Medium
- 131 Palindrome Partitioning 49.2% Medium
backtrack to get all palindrome substr partitioning.
- 132 Palindrome Partitioning II 30.7% Hard
find the min num cut so that every partition is a palindrome.
try every palindrome prefix and cut solve the suffix subproblem.
- - 1278 Palindrome Partitioning III 60.2% Hard *****
you can replace some characters in s so that we can divide s into K paldinrome substr.
base case: all prefix using k=1 get the cost matrix. dp[i][1] all given.
- 53 Maximum Subarray 47.2% Easy
- 152 Maximum Product Subarray 32.4% Medium
- 918 Maximum Sum Circular Subarray 34.0% Medium
- 813 Largest Sum of Averages 50.6% Medium
- 1043 Partition Array for Maximum Sum 66.4% Medium
- 1105 Filling Bookcase Shelves 57.9% Medium
- 1335 Minimum Difficulty of a Job Schedule 58.5% Hard
- 1478 Allocate Mailboxes 55.1% Hard example
-1278 Palindrome Partitioning III 60.2% Hard *****
replace some chars to partition into k palindrome substr at the minimal cost.
approach:
- dp[i,k] represents the min cost for prefix string length =i and k parts
- current char as a palindrome substr dp[i,k]=dp[i-1,k-1]
- current char attached to previous until j, up to k-1 length (each single char as a palindrome substr)
dp[i,k]=min(dp[i,k],cost[j,i]+dp[j-1,k-1])
int palindromePartition(string s, int K) {
int n=s.size();
vector<vector<int>> dp(n+1,vector<int>(n+1,INT_MAX));
vector<vector<int>> cost(n,vector<int>(n));
for(int i=0;i<=n;i++) dp[i][i]=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++)
cost[i][j]=calc_cost(s,i,j);
}
for(int i=1;i<=n;i++) dp[i][1]=cost[0][i-1];
for(int k=2;k<=K;k++){
for(int i=k+1;i<=n;i++){ //length > k
for(int j=i;j>=k;j--){ //previous >=k-1 chars
dp[i][k]=min(dp[i][k],cost[j-1][i-1]+dp[j-1][k-1]);
}
}
}
return dp[n][K];
}
int calc_cost(string& s,int i,int j){
int ans=0;
while(i<j) ans+=s[i++]!=s[j--];
return ans;
}5. Ending with
ending with type of elements, ending with current element et al.
ending with type of elements are often used to reach unique combinations.
- 730. Count Different Palindromic Subsequences *****
- 1682. Longest palindromic subsequence II
- 413 Arithmetic Slices 58.3% Medium
- 446 Arithmetic Slices II - Subsequence 33.0% Hard
- 795 Number of Subarrays with Bounded Maximum 46.9% Medium
- 467 Unique Substrings in Wraparound String 35.9% Medium - 940 Distinct Subsequences II 41.5% Hard
find number of distinct subsequence of S.
int distinctSubseqII(string S) {
int endwith[26]={0};
int mod=1e9+7;
for(int i=0;i<S.length();i++)
{
int t=0;
for(int j=0;j<26;j++)
t+=endwith[j], t%=mod;
endwith[S[i]-'a']=t+1;
}
return accumulate(endwith,endwith+26,0LL)%mod;
}5.interlaced two states
You can use two states and loop each element to update the two states. This is often easier and more understandable than other approaches.
- 1186 Maximum Subarray Sum with One Deletion 38.3% Medium
- 801 Minimum Swaps To Make Sequences Increasing 39.0% Medium
- 276 Paint Fence 38.7% Easy
- 376 Wiggle Subsequence 39.9% Medium
- 600 Non-negative Integers without Consecutive Ones 34.3% Hard
- 964 Least Operators to Express Number 44.5% Hard
- 975 Odd Even Jump 41.7% Hard
- 978 Longest Turbulent Subarray 46.6% Medium Example:
-1524 Number of Sub-arrays With Odd Sum 38.9% Medium
define two states, odd and even.
if current element is odd, then odd[i]=even[i-1]+1 (itself is an odd subarray), even[i]=odd[i-1] (odd+odd->even)
int numOfSubarrays(vector<int>& arr) {
int n=arr.size();
vector<int> odd(n),even(n);
int mod=1e9+7;
odd[0]=arr[0]%2;
even[0]=!odd[0];
int ans=odd[0];
for(int i=1;i<n;i++){
if(arr[i]%2){ //current odd
odd[i]=even[i-1]+1; //itself
even[i]=odd[i-1];
}
else{ //even
even[i]=even[i-1]+1;
odd[i]=odd[i-1];
}
even[i]%=mod,odd[i]%=mod;
ans+=odd[i],ans%=mod;
}
return ans;
}Please upvote if you think it is helpful!