Solving Interesting Numbers

Numbers are not interesting. Yet, someone think that it is interesting to put a definition on everything. Today, let’s take a look at this slightly annoying Interesting Number puzzle.

The puzzle

Here comes the definition: numbers are considered interesting if and only if:

It only consists of 0, 1, 2, and 3
0 must come before 1
2 must come before 3
0 must not be the first digit

2013, for example, is considered interesting. Of course, when there are only four digits, there are other equally interesting numbers: 2301 and 2031.

And this raises us the question: given $n$ as the number of digits, please count the number of interesting numbers $i$ . That means when $n = 4$ , $i = 3$ .

CodePad!

Well, feel free to play around in this spoiler-free area:

CodePad

                "use strict";
                
CodePad Help
Use `log(...)` to log stuffs to the output window.
Use `canvas` to access the canvas (if it exists).
Use `ctx` to access the canvas' 2D context (if it exists).
Whenever you press "run" or "canvas", the code will be rerun.
Code
Run
Canvas
Help

Spoiler-free image

Also, before you accidentally peek into the answer, please take a look at this beautiful flamingo:

Flamingo!

And here comes the REAL blog!

Alright. Now that you’ve tried (did ya?) and appreciated the flamingo (yeah you did), you must be eager to know the answer! Well me too! This puzzle is said to be easier if you know about Dynamic Programming (aka DP). As Wikipedia said, it is both a mathematical optimization method and a computer programming method. It works by simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. Our puzzle could also be solved in this way.

But how?

Now that’s a pretty good question. But first, let’s look at it from a recursive angle: