be_right_back_in_2018's blog

DP Easy Question
By be_right_back_in_2018, history, 9 years ago, In English

Hi, Codeforces!

I have a question that most of you might find it very easy, about problem 489C - Даны длина и сумма цифр...

I'm actually still a newbie at solving Div2-C problems, since then I would be very glad if someone of you can help me with my question.

The question is: How does the DP approach of this problem differ than the greedy one written in problem's tutorial?

Thanks all, thanks in advance for this great community funded by your contributions!

Good luck with today's round btw ;)

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
9 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

The DP approach applicable here is commonly known as Digit DP. Here, you consider the number as a decimal string and add digit after digit for each index and eventually at index m check whether current summation of digits equals to s or not. Hence the states would be index and currentSum. For maximizing, start adding numbers from 9 to 0 and for minimizing do the opposite with a check that you don't add leading zeros. Finally print the DP solution to get the desired output.

Here are some good Digit DP problems.

→ Reply