1. Every number as a string of digits

Let size be the number of digits of $n$. Write every number from 0 to $n$ with exactly size digits, adding zeros on the left when it is shorter. For $n = 13$ the numbers become 00, 01, ..., 13. The added zeros hold no 1, so the count of 1s does not change.

Now every number is one choice of a digit for each position, read from left to right. The code counts the 1s in all these digit strings that are at most $n$.

The code's function count(pos, ones, tight) answers one question. Digits have already been chosen for positions 0 to pos - 1, and they hold ones digits equal to 1. Over every way to finish the string that keeps the number at most $n$, how many 1s do the finished numbers hold in total? The answer to the whole problem is count(0, 0, True).

2. One step: choosing the digit at pos

The digit $d$ at position pos can be any value from 0 to top. Each choice adds $1$ to ones when $d = 1$:

$\text{count}(pos, ones, tight) = \sum_{d=0}^{top} \text{count}\big(pos + 1,\ ones + [d = 1],\ tight \text{ and } d = top\big)$

Here $[d = 1]$ is 1 when $d = 1$ and 0 otherwise. At the end of the string, pos == size, and the finished number holds exactly ones 1s, so count returns ones.

The flag tight decides top:

3. Why every number is counted once, and why memoization works

Two numbers with the same size digits compare like words in a dictionary. The first position where they differ decides which is smaller. So a string stays at most $n$ exactly when, at the first position where it leaves $n$'s digits, it takes a smaller digit. The tight flag follows this rule. While tight is True, the digit may not exceed $n$'s digit. Once a smaller digit is chosen, the number is already less than $n$, and every later digit is free. So each number from 0 to $n$ is one path of choices, and no other path is allowed.

The answer of count depends only on its three arguments, not on which digits led there. So @lru_cache stores each answer once. There are at most size + 1 values of pos, at most size + 1 values of ones and 2 values of tight. Each state loops over at most 10 digits. This gives the docstring's $O(D^2 \cdot 10)$ time with $D$ = size.

A side note, not the code on this card: when tight is False, the free part has a closed form. Say $m$ = size - pos positions are left. Each of the $10^m$ endings adds the ones 1s already chosen. In each of the $m$ positions, the digit 1 appears in exactly $10^{m-1}$ of the endings. So the total is $ones \cdot 10^m + m \cdot 10^{m-1}$. Other solutions count, for each digit position of $n$, how many numbers from 0 to $n$ have a 1 there. They use a formula built from the digits of $n$ above, at and below that position. The recursion on this card needs no such formula. It adds up the same counts one digit at a time.

4. The digit equal to top, and $n = 0$

tight and d == top keeps the flag only on the digit equal to top. If the code set the flag to True for every $d$, it would forbid endings that are in the range. For $n = 20$ it would then allow only 00, 10 and 20, and return 1 instead of 12. If it set the flag to False for every $d$, it would allow endings above $n$. For $n = 13$ it would then also count 14 to 19, and return 12 instead of 6.

The loop is range(top + 1), so $d$ can equal top. The + 1 makes $n$ itself part of the count, as the problem's "from 0 to n, both ends included" requires.

For $n = 0$, digits is [0]. The only choice is $d = 0$, which holds no 1, so the code returns 0. This is Example 2.

5. Example 1 by hand

n = 13, so digits = [1, 3] and size = 2. The call count(0, 0, True) has top = 1, so it tries $d = 0$ and $d = 1$.

The first row is not tight, because 0 is smaller than $n$'s first digit 1. So its last digit may be anything from 0 to 9. The second row is tight, because its first digit equals $n$'s first digit. So its last digit may not pass 3. The side note agrees with the first row: with ones = 0 and $m = 1$, the total is $0 \cdot 10 + 1 \cdot 10^0 = 1$.

count(0, 0, True) returns $1 + 5 = 6$, the expected output. The six 1s are in 1, 10, 11 (two of them), 12 and 13.

6. From the recursion to the code