Note: This blog was polished with the help of AI, but the learning goals and problem collection reflect my own practice journey.

CM is my next milestone on the road toward Master/IM, and I'm trying to improve the way I approach DP problems along the way. Knowing standard patterns is one thing, but figuring out the state in an unfamiliar problem is a different challenge.

I want to get better at deriving states and transitions instead of relying only on patterns I've seen before. Here's the approach and practice progression I'm following.

Here's what I'm trying to focus on

1. Build a base, then move beyond standard problems

Get comfortable with basic recurrence, memoization, knapsack, grid DP, and LIS. But don't stop once you can solve the standard versions. Try problems where the state or transition isn't obvious.

2. Learn to identify when DP might fit

Look for problems involving minimum or maximum costs, counting ways, or finding the longest or shortest valid sequence. Think about whether smaller subproblems repeat and whether their answers can help solve the original problem. These are useful clues, but similar problems can also have greedy or mathematical solutions.

3. Don't guess the state

Before writing dp[i] or dp[i][j], think about what information you need to solve the remaining problem. Starting with brute force and identifying the available choices can help, but the tricky part is finding a state that captures enough information without making the solution unnecessarily complex.

A few small DP examples

1. Basic DP — Fibonacci

dp[0] = 0;
dp[1] = 1;

for (int i = 2; i <= n; i++)
    dp[i] = dp[i-1] + dp[i-2];

Here, the state is straightforward: dp[i] stores the (i)-th Fibonacci number. The next state depends on the previous two.

2. Think about the choices — Maximum sum without adjacent elements

dp[i] = max(dp[i-1], dp[i-2] + a[i]);

At each position, either skip the current element or take it and add the best answer that doesn't include the previous element. The important part is understanding why these choices cover every possibility.

3. State design — Knapsack

for (int i = 0; i < n; i++)
    for (int j = w; j >= wt[i]; j--)
        dp[j] = max(dp[j], dp[j-wt[i]] + val[i]);

Here, dp[j] stores the maximum value achievable with capacity at most j. Iterating backward ensures each item is used at most once.

These examples are simple, but the questions behind them are what matter: What does the state represent? What choices lead to it? And why does the transition work?

4. Make upsolving count

When I can't solve a problem, I want to figure out why. Was I unable to recognize DP, did I define the wrong state, or could I not derive the transition? These are different problems, and simply solving more questions might not fix them.

My planned practice progression

1. Basic DP and memoization
2. Knapsack and subsequences
3. DP with less obvious states
4. Mixed-topic problems where you must identify DP yourself.

A collection of 50 DP problems worth exploring

I've collected these problems from different rounds and difficulty levels. I'm sharing them as a practice collection, not a ranking, and some require ideas beyond conventional DP.

I'd revisit the problems I couldn't solve independently after a few days. Being able to derive the solution again without the editorial is a good sign that I've actually learned something.

For those who've reached Expert or beyond, what helped you improve at DP the most? Was it practice, learning to derive states, or something else?