The CSES book has a really good introduction to Dynamic programming. I'm not sure if this is the best approach, but I tend to look for 2 things

• Overlapping (or Reoccuring) substates
• Recursive Formula

In general, once you find these this should be easy.

So take a look at this problem, in the beginning you have a ribbon of length n, and you can cut it into pieces of length A, B, C. You should find the maximum amount of pieces you can cut.

Let's look at a recursive formula. C = Length of String/Ribbon so far calc(C) = recursive function to calculate maximum amount of ribbons we can take from C

ans = max(Calc(C-A), Calc(C-B), Calc(C-C)) + 1

Here are some base cases if(C < 0) return negative infinity because it's impossible to make a ribbon piece with negative length

else if(C == 0) return 0 because there is no other way we can make the string given A B and C are positive

else if(C > 0) return ans (basic recursive formula)

Since it is guaranteed to be able to cut a piece this way, it guaranteed that In general, this is the solution. The running time is T = [3*T(N) + O(1) (for constant ops)] or 3^n.

But notice, if we can have overlapping substates (Imagine what happens when we have 2 and 1 (like fibonacci) ). (Too much effort to put in a comment, but I will just state that). So we can store these states in an array (memoization). We can set each value in the memo array to -1 just to clarify if we have used this state before. and check if this value exists. If not we can set this memo value. Since each memo value gets used once (or checked), the running complexity becomes the number of values in the memo array after it is precalculated.

Thus we can reduce the complexity to [3*T(N) + O(1)] to T = [T(N) + 1] or O(N).

In case you are confused, I have attached my submission link to the problem.

https://codeforces.me/contest/189/submission/112180784

Hope this clarifies things a bit, good luck on your CP journey! DP is definitely a hard topic, for sure!

some more insight for you:

Identifying a DP problem

• First check the constraints of the problem. If they seem pretty small there could be a DP solution.

• If there is a constraint which practically could be any value but limited to like 1e5 in the statement, that's also a hint

  -Eg: Let's consider a hypothetical problem involving juices and their sweetness, sweetness being 1e9 doesn't seem like an obstacle at first. But if it's limited to 1e5 it could be used in a state for our DP

Developing the solution

• Think of the simplest version of the problem. Like when $$$n=1$$$. That's the base case. You must be able immediately answer this case. (in constant time)
• Imagine how you're going to increase values gradually and reach the full solution
• Consider a position where you're some where middle in the solution. Think what are the minimum data you need to extract everything you need to know about current location. This is the state of the DP.
• Think how are you going to reach another location from the point you're currently in. It's the transition of your DP.

Now you can start from the base state and transition to every stage you can until you reach the complete solution.

Eg:-

Given an Integer array $$$a$$$ $$$(a_i \gt 0)$$$ of length $$$n$$$ $$$(n \lt =10^2)$$$ find the length of the longest subset such that their sum does not exceed $$$w$$$ $$$(w \lt =10^4)$$$

Identifying if this is DP

$$$n$$$ seems pretty low. That's interesting. If there's a greedy solution $$$w$$$ being like $$$10^9$$$ won't be a problem. But it is $$$10^4$$$. $$$n*w=10^6$$$ which is approximately the maximum size of a local array. So far constraints suggest a DP problem.

Developing the solution

if $$$w=0$$$ answer would be $$$0$$$ as we cannot use any element. We can use that as the base case. Let's start the base case from the first element. Then we'll consider two elements, Then three elements and so on.

When i'm in the middle of the solution what would i need to store?

1. what's the current element i'm focusing on
2. How much of $$$w$$$ i have already used

This is our state. There are $$$n$$$ elements so size of this would be $$$n*w=10^6$$$ .

$$$DP_i,_j=$$$ Length of the longest subset we can make considering the first $$$i$$$ elements without their sum being $$$j$$$

Now how are we going to reach the complete solution? Where can we go from $$$DP_i,_j$$$ .As we are considering elements in order next we'll have to got to $$$i=i+1$$$. We can either include this element in our subset or not. If we don't include it we can go to $$$DP_{i+1,j}$$$ And the length won't change. If we include this element we can go to $$$DP_{i+1,j+a_{i+1}}$$$ And length will increase in $$$1$$$

Reversing these two operations we can get,

$$$DP_{i,j}=$$$ $$$max(DP_{i-1,j},DP_{i-1,j-a_i}+1)$$$

Now our solution is complete. Considering DP as a 2D array i think this is fairly easy to implement.