| Trick | Difficulty | |
|---|---|---|
| LC 1092. Shortest Common Supersequence | DP in Linear Structures (Two Arrays) + Backtracking + Greedy | 6 points |
| LC 1143. Longest Common Subsequence | DP in Linear Structures (Two Arrays) | 5 points |
| LC 727. Minimum Window Subsequence | DP in Linear Structures (Two Arrays) | 6 points |
| LC 920. Number of Music Playlists | DP in Linear Structures (Extra States) | 6-7 points |
| LC 1444. Number of Ways of Cutting a Pizza | DP in Linear Structures (2D Matrix) + Extra States | 6 points |
| LC 1449. Form Largest Integer With Digits That Add up to Target | DP in Linear Structures + Knapsack + Get Real Result (Greedy) | 6 points |
| LC 368. Largest Divisible Subset | DP in Linear Structures + Backtracking + Greedy | 5-6 points |
| LC 1473. Paint House III | DP in Linear Structures (Extra States) | 6 points |
| LC 1458. Max Dot Product of Two Subsequences | DP in Linear Structures (Two Arrays) | 5-6 points |
| LC 1425. Constrained Subsequence Sum | DP in Linear Structures + Monotonic Queue (or Priority Queue) | 6 points |
| LC 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons | DP in Linear Structures (Extra States) | 6 points |
| LC 1416. Restore The Array | DP in Linear Structures | 6 points |
| LC 1406. Stone Game III | DP in Linear Structures | 6 points |
| LC 1402. Reducing Dishes | DP in Linear Structures (Extra States) | 6 points |
| LC 1388. Pizza With 3n Slices | DP in Linear Structures (Extra States) + Circular Array | 6 points |
Category: DP in Linear Structures
DP in Linear Structures (Extra States)
Posted on
Summary In some problems, the index i is not enough to make subproblems alg[i] independent to the previous sequences s[0,i-1]. We need one or several extra states to make subproblem self-contained. The intuition is: if we brute force the problem, there might be many duplicate visitings. For example, two different dfs enter the same index…
Monotonic Queue in DP
Posted on
Summary In this post, I will introduce some DP problems involving the Monotonic Queue. Details LC 1425. Constrained Subset Sum It is not difficult to get the following O(n^2) solution. However, the complexity is not good. What we need for {alg[i+j] for j=[1, k]} is only the maximum. So we need to keep tracking the…
Reduce Time Complexity in DP
Posted on
Summary In this post, I will introduce some DP problems. It might not be difficult at the first glance. However, the optimal solution might have lower complexity if one carefully defines the state or uses some other techniques while transferring states. OJ Details LC 1027. Longest Arithmetic Sequence It is not difficult to get the…
Hard-to-Detect DP
Posted on
Summary In this post, I will introduce some problems that seem difficult. But once we think of them in another way, they will become DP problems in linear structures or intervals, which are not difficult to solve. OJ Details LC 1049. Last Stone Weight II Think of it in this way: we divide the numbers into…
Palindrome & DP
Posted on
Summary In this post, I will introduce some problems related to palindrome and dynamic programming. A palindrome has a property that, if we add two equal characters in both side of it, it is still a palindrome. OJ Details LC 1278 Palindrome Partitioning III Difficulty: 6-7 points Given a string s containing lowercase letters and an integer k….
DP in Linear Structures & Real Result
Posted on
Summary Some problems require returning real result not just a number. To do this, a good method is that we create another table to store the optimal choices we made on each state. To return any optimal result, the choice table will be as large as the alg table. The result can we achieved by…