Atcoder contest abc154 Digit DP Question Problem E

Revision en1, by yesnomaybe, 2020-07-05 23:50:18

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English yesnomaybe 2020-07-05 23:50:18 922 Initial revision (published)