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.

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 as the number of digits, please count the number of interesting numbers . That means when , .

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

CodePad

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

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

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.

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