de_dust2's blog

By de_dust2, history, 5 weeks ago, In English,

Problem link : https://atcoder.jp/contests/abc154/tasks/abc154_e

Can someone please explain what does the dp state denote in this solution? Solution Link : https://atcoder.jp/contests/abc154/submissions/9982527

I was able to solve the question using recursive (+ memoization) approach. My solution : https://atcoder.jp/contests/abc154/submissions/15031609

My approach : solve(i, res, k) — At position i, if there's a restriction on digit at this position, and number of non-zero digits remaining to be taken.

But am not able to understand the iterative dp approach. Sorry my peanut brain is not able to understand. If someone could please explain what does the state denote & why it works? (need explanations in terms of intuition and not in code or mathematics sense). Because it seems like coding iterative is much faster and simpler.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

It isn't DP.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It's a standard Digit DP technique, please, see here.