I’m trying to optimize my solution for this problem: Codeforces 2036F. If anyone has solved it using DP, I would appreciate your help.

I’m working on optimizing the recursive DP solution.

Initially, I got an accepted solution using a 5-state DP: (index, fixed_on_digit, states to handle the boundaries and conditions...). This DP function returns the number of numbers where fixed_on_digit == 1, starting at each index.

Here’s the submission link for my initial solution: Accepted Solution.

Now, I’m trying to remove the fixed_on_digit state to simplify the solution. I saw this comment, which suggests using an extra DP table to get rid of the fixed_on_digit state. However, I can’t fully understand what he is doing there.

Currently, I’ve written a very clean implementation, but the remaining part is the memoization logic. Here’s the code I’ve written so far: Code

This code can return the number of numbers where the current digit == 1, but only starting from the current index till the 0th index

Can someone help me figure out how to implement the remaining part