DSA 8 - DP and Greedy Patterns

Background

I’ll go over some pains I’ve had, then create a question list to explore to get better at greedy.

My ELO has essentially been hardstuck for a while because when I see an intermediately difficult greedy problem I sort of give up. The solution always feels very random to me, and it could also be DP. An example is uncrossed lines, which I thought was a greedy at first because the state looked too big, then it was a DP. Sometimes it’s too easy, like maximize points after choosing K tasks I did almost instantly because I happened to see the solution. Or it feels like an obscure greedy pattern like maximum number of weeks then you look at the comments and its people complaining that you should ‘just know’ the answer.

I’m not going to be writing about how to solve all greedy problems, just thoughts about it, then an attempt to break them into categories.

Establishing DP vs Greedy

The worst part of this is people will just say it’s intuition that you build, and the obscure greedy problems never really end. The easiest way to rule out DP is to check your time complexities. DP will put forwards some small maximum space bound, and that can be a hint, then you calculate that effectively brute forcing the problem is still fast enough. Most problems can be identified like that, like coin change, jump game, or gas station.

However, sometimes your state seems cursed. In the last examples, your state could be summarised very shortly. In uncrossed lines, the pain I was having was I’d try to grow from previous states, where each state is a line. So for each line, I’d compare to every previous line, check whether it’s allowed to grow off it, and then try.

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        n, m = len(nums1), len(nums2)
 
        grid = [[0 for _ in range(m)] for _ in range(n)]
 
        for i, j in product(range(n), range(m)):
            extra = 1 if nums1[i] == nums2[j] else 0
            grid[i][j] = max(grid[i][j], extra)
            for x, y in product(range(i), range(j)):
                if i > x and j < y:
                    continue
                grid[i][j] = max(grid[x][y] + extra, grid[i][j])
 
        best = 0
        for row in grid: best = max(best, max(row))
        return best

The fundamentally wrong thing here is that I didn’t start with the recursion. I tried to do the solution directly on the grid representation, and I didn’t identify that I don’t need to look at all previous states.

Think about what you need for your current state, and how your current state moves forwards. In this case you can move i forwards, or j, or both. So your current state is just $(i,j)$, and this $(i,j)$ has some previous state that was optimal that you took. DP itself is very doable, the issue is just when you’re confusing it for greedy.

Greedy Patterns

Let’s go over some classical greedy problems, then break them into patterns. This list is from the neetcode roadmap, leetcode patterns, and some from the greedy leetcode list.

If it’s your first time seeing these, it’s ok. I propose this set should be studied for a basis of greedy problems, rather than

1. Interval Management
   1. Video Stitching
   2. Set Intersection Size At Least Two
2. Deadline & Scheduling
   1. Course Schedule III
   2. Minimum Number of Refueling Stops
3. Lexicographical String Construction
   1. Remove Duplicate Letters
   2. Smallest Subsequence of Distinct Characters
4. Monotonic Stack Construction
   1. Remove K Digits
   2. Create Maximum Number
5. Tree-Based Greedy
   1. Binary Tree Cameras
   2. Distribute Coins in Binary Tree
6. Constructive Arrays
   1. Patching Array
   2. Consecutive Numbers Sum
7. Allocation & Binary Search on Answer
   1. Split Array Largest Sum
   2. Capacity To Ship Packages Within D Days
8. Two-Dimension & Sorting
   1. Queue Reconstruction by Height
   2. Russian Doll Envelopes
9. Graph-Based Greedy
   1. Min Cost to Connect All Points
   2. Path With Minimum Effort
10. Cost/Profit Optimization
    1. Best Time to Buy and Sell Stock with Transaction Fee
    2. IPO
11. Meeting Rooms & Resource Allocation
    1. Meeting Rooms II (Premium)
    2. Car Pooling
12. Greedy with Subsequences
    1. Wiggle Subsequence
    2. Longest String Chain
13. Simulation & Arrangement
    1. Gas Station
    2. Advantage Shuffle
14. Frequency & Spacing
    1. Task Scheduler
    2. Reorganize String
15. Mathematical Optimality
    1. Integer Break
    2. Minimum Moves to Equal Array Elements II
16. Partitioning & Grouping
    1. Partition Labels
    2. Minimum Number of Arrows to Burst Balloons
17. Swap Optimization
    1. Minimum Swaps to Group All 1’s Together II
    2. Minimum Adjacent Swaps to Reach the Kth Smallest Number
18. Backward Processing
    1. Check If String Can Break Another String
    2. Jump Game II
19. Palindrome Construction
    1. Construct K Palindrome Strings
    2. Longest Palindrome by Concatenating Two Letter Words
20. Parentheses & Balancing
    1. Minimum Add to Make Parentheses Valid
    2. Minimum Insertions to Balance a Parentheses String

Conclusion

Most other websites just describes greedy as “taking the next best move” and you need to think creatively to find that. I’m proposing a set of questions that can be studied to begin with. You can study the first, then solve the second.