Dynamic Programming States Doubt!

Правка en1, от your.nemesis, 2021-12-06 16:57:18

I have had this doubt in dynamic programming for a long time now regarding which states to use. The question goes something like this:

Reading Input:

Recursion Code: So from the basic intuition I wrote this code. Which is obviously MLE:

Then I tried this code:

And this code passed the test cases and got AC. So now coming back to my doubt. There have been many problems where

$$$ dp[i][j][k] --> $$$ is optimized to $$$--> dp[i][j] $$$ because the state j is always changing. But I have also practiced questions where trying this $$$ dp[i][j][k] --> $$$ is optimized to this --> $$$ dp[i][j] $$$ and it got me a WA.

So can someone please explain when to take a state into consideration so that I dont fall into this MLE trap again in the near future?

Thank you:)

Теги dp, dynamic programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский your.nemesis 2021-12-06 16:57:18 1181 Initial revision (published)