I'm reviewing DP and I was wondering the intuition behind determining the subproblems for some DP problems.

For example, consider 2 similar problems.

Given a set of 1, 2, and 3 steps you can take, find the total number of ways to reach X steps.

Given a set of 1, 2, 3 coins, find the total number of ways to reach X amount.

After doing both problems, I've found that the main difference in the problems is that for coins, order does not matter. If you have 1 coin and 3 coin, it's the same as if you have a 3 coin and 1 coin. With steps, order matters. Taking 1 step then 3 step is different than taking 3 step then 1 step.

With that, the correct subproblem it seems for the coins is given 1 coin, how many ways can we reach X amount. Thus you build out your solution first with 1 coin, then add a coin, and then add a coin.

With the stairs problem, it seems like the subproblem is given a set of stairs with just 1 step, how many ways can we climb up. Then do it for 2 steps, and so on until you reach X.

I'm wondering if there's some intuition behind how to choose these subproblems. It seems like just as easily, you could say for the stairs problem the subproblem can be given the ability to take 1 step only, how many ways are there to climb up X steps. Now add the ability to take 2 steps, and so on.

Any tips to think through these problems would be greatly appreciated!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.