joaquimnt_'s blog

By joaquimnt_, history, 4 years ago, In English

I am trying to solve this problem:

At first, my references was these posts: and

But i am getting problems when i try to save the results into a dp table. Can someone tell what are the states of my memoization?

My code (the parts with memoization are commented):

My strategy is: for each digit, compute the number of its occurrences in F(B) and in F(A — 1). The answer (for that digit) is computed by F(B) - F(A - 1). Without dynamic programming techniques, it solves the problem, despiste the slowness. Some problems that i solved earlier got accepted with the following states: dp[current_digit][number_formed][leftmost_lo][leftmost_hi], but in this particular problem, the number formed might be to high.

Read more »

  • Vote: I like it
  • -8
  • Vote: I do not like it