When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

yesnomaybe's blog

By yesnomaybe, history, 4 years 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

| Write comment?