Problem 117: Red, Green, and Blue Tiles

Project Euler Problem 117 Solution

EulerSolve provides an optimized solution for Project Euler Problem 117, Red, Green, and Blue Tiles, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We must tile a row of length 50 using grey unit squares together with red tiles of length 2, green tiles of length 3, and blue tiles of length 4. Every arrangement has to cover the row exactly, with no overlap and no overhang, so the question is how many distinct complete tilings exist. The all-grey arrangement is included, because grey squares are valid pieces. What makes this problem different from the earlier single-colour variants is that red, green, and blue tiles may be mixed freely in the same row. That turns the task into a counting problem on compositions of 50 with allowed part sizes $1,2,3,4$, where the size-1 part represents one grey square. Mathematical Approach Let $T(n)$ denote the number of legal tilings of a row of length $n$. The required answer is therefore $T(50)$. The useful state is just the remaining length, because once that length is known, the earlier part of the row no longer affects the number of ways to finish it. Choose the right state space A tiling of length $n$ can be read as a sequence of piece lengths whose sum is $n$. Since the available lengths are exactly $1,2,3,4$, each valid arrangement corresponds to a composition of $n$ with parts in $\{1,2,3,4\}$. No extra colour factor is needed: there is exactly one tile type of each non-grey length....

Detailed mathematical approach

Problem Summary

A row of length $n$ units has to be covered exactly, with no gaps, overlaps or overhang, by grey squares of length $1$, red tiles of length $2$, green tiles of length $3$ and blue tiles of length $4$. Any number of tiles of each kind may be used, colours may be mixed, the same tiles in another order make another tiling, and the all-grey row counts too. A row of five units has exactly $15$ tilings, and we must find the number of tilings of a row of fifty units. ^[1] The statement links it to Problem 116, which uses the same tiles but forbids mixing colours and needs at least one coloured tile. ^[2]

The whole solution in one sentence: the last tile is $1$, $2$, $3$ or $4$ units long and leaves a tiling of a row that much shorter, so each count is the sum of the four counts before it, and fifty steps of this rule, starting from the single tiling of the empty row, give the result.

Mathematical Approach

Write $T(n)$ for the number of tilings of a row of length $n$; the statement gives $T(5)=15$, and we want $T(50)$.

1. Tiny rows by hand

We describe a tiling by the lengths of its tiles from left to right, joined by plus signs: $1$ is a grey square, $2$ a red tile, $3$ a green tile and $4$ a blue tile. For example, $1+2+2$ is a grey square followed by two red tiles. There is exactly one kind of tile of each length, so this list describes the tiling completely.

Length $1$: only $1$, so $T(1)=1$.
Length $2$: $1+1$ and $2$, so $T(2)=2$.
Length $3$: $1+1+1$, $1+2$, $2+1$ and $3$, so $T(3)=4$.
Length $4$: $1+1+1+1$, $1+1+2$, $1+2+1$, $2+1+1$, $2+2$, $1+3$, $3+1$ and $4$, so $T(4)=8$.

The counts $1,2,4,8$ double at every step. Section 3 shows why, and why the doubling stops at length $5$.

2. The fifteen rows of length five

Here are all $15$ tilings of a row of five, sorted by the number of tiles:

two tiles: $1+4$, $4+1$, $2+3$, $3+2$;
three tiles: $1+1+3$, $1+3+1$, $3+1+1$, $1+2+2$, $2+1+2$, $2+2+1$;
four tiles: $1+1+1+2$, $1+1+2+1$, $1+2+1+1$, $2+1+1+1$;
five tiles: $1+1+1+1+1$.

Without the all-grey row there would be only $14$, so the $15$ of the statement confirms that this row counts. Under the rules of Problem 116 the row of five has $7$ tilings with red tiles, $3$ with green and $2$ with blue tiles; ^[2] the present problem adds the all-grey row and the mixed rows $2+3$ and $3+2$, and $12+3=15$.

3. Cutting the row into pieces

Think of a row of length $n$ as $n$ unit cells with $n-1$ inner boundaries. A tiling is the same as a choice of the boundaries at which one tile ends and the next begins: $1+2+2$ cuts after the first and the third cell. If pieces of any length were allowed, a yes or a no at each boundary would give $2^{n-1}$ tilings; these ordered ways of writing $n$ as a sum of positive whole numbers are the compositions of $n$. ^[3]

Our tiles are at most $4$ units long, so a choice is allowed exactly when it never leaves four consecutive boundaries uncut. For $1\le n\le4$ no piece can be longer anyway, so $T(n)=2^{n-1}$, the doubling of Section 1. For $n=5$ only the uncut row $5$ is forbidden, so $T(5)=16-1=15$; for $n=6$ the forbidden ones are $6$, $1+5$ and $5+1$, so $T(6)=32-3=29$. Longer rows get messier, but a bound from below is easy: split the row into pairs of cells, fill each pair with two grey squares or one red tile, and a leftover cell, when $n$ is odd, with a grey square. Different choices give different tilings, so, with $\lfloor n/2\rfloor$ the whole part of $n/2$,

$$2^{\lfloor n/2\rfloor}\le T(n)\le2^{n-1}\qquad(n\ge1).$$

4. Listing every tiling is hopeless

The most direct program builds the tilings tile by tile: a recursive function tries every tile that still fits as the next one, continues with the rest of the row, and returns $1$ for an empty row. It reaches every tiling separately, so its work is at least $T(n)$: it makes $590081$ calls for $n=20$, where $T(20)=283953$, and $417825921$ for $n=30$, where $T(30)=201061985$, and a row of fifty about $5\cdot10^5$ times as many as a row of thirty. Yet the same rest of the row is counted again and again, once for every way of tiling the part in front of it.

5. The last tile decides: a recurrence

Look at the last tile of a tiling of a row of length $n\ge1$. It has length $k=1$, $2$, $3$ or $4$, and removing it leaves a tiling of length $n-k$; conversely, a tile of length $k$ put after any tiling of length $n-k$ gives a tiling of length $n$ whose last tile has length $k$. These operations undo each other, so the tilings of length $n$ ending with a tile of length $k$ are exactly as many as the tilings of length $n-k$. The four groups do not overlap and together contain every tiling, so for every $n\ge1$

$$\begin{aligned}T(n)={}&T(n-1)+T(n-2)\\&+T(n-3)+T(n-4).\end{aligned}$$

Two conventions make this rule correct for small $n$. A tile cannot stick out, so $T(m)=0$ for $m\lt0$. And $T(0)=1$: the empty row has exactly one tiling, the one without tiles. Removing the only tile of the tiling $2$ leaves the empty row, and that tiling must be counted once; with $T(0)=0$ and $T(1)=1$ the rule would give $T(2)=1$ and lose it.

For $n=5$ the rule gives $T(5)=8+4+2+1=15$: in the list of Section 2, eight tilings end with a grey square, four with a red tile ($1+1+1+2$, $2+1+2$, $1+2+2$, $3+2$), two with a green tile ($1+1+3$, $2+3$) and one with a blue tile ($1+4$).

6. Dynamic programming

Dynamic programming is the general name for this idea: when a problem is built from smaller versions of itself and the same smaller versions are needed many times, each one is solved once and stored. ^[4] Here the smaller versions are the shorter rows. Starting from $T(0)=1$, we fill a table for $n=1,2,3,\dots$, each entry from the four before it. For $n=0,1,\dots,20$ it reads

$1$, $1$, $2$, $4$, $8$, $15$, $29$, $56$, $108$, $208$, $401$, $773$, $1490$, $2872$, $5536$, $10671$, $20569$, $39648$, $76424$, $147312$, $283953$.

For example, $T(10)=208+108+56+29=401$. The steps for $n=1,2,3$ need $0$, $1$ and $2$ additions and every later step $3$, so a row of thirty needs $84$ additions instead of the $417825921$ calls of Section 4, and a row of fifty $144$. This is the bottom-up form of dynamic programming; the top-down form, memoization, keeps the recursive function but stores each result the first time it is computed. ^[4]

Sections 1 to 6 contain everything the programs use. Sections 7 to 12 look at the same numbers in other ways, which also gives independent checks, and list the pitfalls of an implementation.

7. A second recurrence: almost doubling

A tiling of length $n\ge2$ also arises from a tiling of length $n-1$ in one of two ways: put a grey square after it, or make its last tile one unit longer. The first way gives every tiling of length $n$ that ends with a grey square, the second every tiling whose last tile is at least $2$ long, each exactly once, because removing the square or shortening the tile undoes the step. But a blue last tile cannot grow, and the tilings of length $n-1$ ending with a blue tile are as many as the tilings of length $n-5$. Therefore, for every $n\ge2$,

$$T(n)=2\,T(n-1)-T(n-5).$$

For example $T(5)=2\cdot8-1=15$ and $T(10)=2\cdot208-15=401$. For $n=1$ the rule fails, because the empty row has no last tile to lengthen. Subtracting the recurrence of Section 5 for $n-1$ from the one for $n$ gives the same identity by algebra. ^[5] So the counts almost double: every shorter tiling continues in two ways, unless it ends with a blue tile.

8. Counting by inventory

A third way to count first fixes the inventory of a tiling, how many tiles of each colour it uses: $a$ grey squares and $b$ red, $c$ green and $d$ blue tiles with $a+2b+3c+4d=n$, so $k=a+b+c+d$ tiles in all. If these $k$ tiles were all different, they could be put in $k!=1\cdot2\cdots k$ orders, with $0!=1$. Swapping tiles of the same colour changes nothing, and every tiling arises from exactly $a!\,b!\,c!\,d!$ of these orders, so the number of tilings with this inventory is the multinomial coefficient ^[6]

$$\frac{(a+b+c+d)!}{a!\,b!\,c!\,d!}.$$

For $n=5$ there are six inventories: five grey squares give $1$ tiling; three grey squares and a red tile give $4$, one for each place of the red tile; a grey square and two red tiles give $3$; two grey squares and a green tile give $3$; a red and a green tile give $2$; a grey square and a blue tile give $2$. Indeed $1+4+3+3+2+2=15$. Every tiling has exactly one inventory, so

$$T(n)=\sum_{a+2b+3c+4d=n}\frac{(a+b+c+d)!}{a!\,b!\,c!\,d!},$$

summed over whole numbers $a,b,c,d\ge0$. It needs no earlier counts, but its many terms with large factorials make it a check rather than the method.

9. The tetranacci numbers

Each number of the table is the sum of the four before it, the rule of the tetranacci numbers. ^[7] The tetranacci sequence usually starts $0,0,0,1$ and continues $1,2,4,8,15,\dots$; the On-Line Encyclopedia of Integer Sequences lists it as A000078 and notes that its term with index $n$ counts the compositions of $n-3$ with no part greater than $4$, so $T(n)$ is the tetranacci number with index $n+3$. ^[5] The argument of Section 5 works for any set $S$ of positive tile lengths: with $T_S(0)=1$ and $T_S(m)=0$ for $m\lt0$, it gives $T_S(n)=\sum_{s\in S}T_S(n-s)$ for $n\ge1$, and a length available in several colours contributes its term once per colour. Grey squares and red tiles alone give the Fibonacci numbers $1,1,2,3,5,8,\dots$: the $8$ for a row of five are the $7$ red tilings of Problem 116 and the all-grey row.

10. A generating function

A generating function stores a whole sequence in one expression: $T(n)$ becomes the coefficient of $x^n$ in the power series ^[8]

$$\begin{aligned}F(x)&=\sum_{n\ge0}T(n)\,x^n\\&=1+x+2x^2+4x^3+\dots\end{aligned}$$

The basic example is the geometric series $1+q+q^2+\dots=1/(1-q)$. ^[8] One tile is described by $G(x)=x+x^2+x^3+x^4$, one term for each length. Multiplying power series adds exponents, so the coefficient of $x^n$ in $G(x)^j$ counts the sequences of $j$ tiles with total length $n$; for $n=5$ these coefficients are $4$, $6$, $4$ and $1$ for $j=2,3,4,5$, the groups of Section 2, and expanding $G(x)^j$ with the multinomial theorem gives back the inventory sum of Section 8. ^[6] A tiling is a sequence of any number $j\ge0$ of tiles. Since $G(x)^j$ starts with $x^j$, only $j\le n$ contribute to the coefficient of $x^n$, so the sum over all $j$ is a well-defined formal power series, the geometric series with $q=G(x)$:

$$F(x)=\frac{1}{1-x-x^2-x^3-x^4}.$$

The recurrence says the same: in $(1-x-x^2-x^3-x^4)\,F(x)$ the coefficient of $x^n$ is $T(n)-T(n-1)-\dots-T(n-4)$, which is $0$ for $n\ge1$ and $1$ for $n=0$. Multiplying the numerator and the denominator by $1-x$ gives the second form $F(x)=(1-x)/(1-2x+x^5)$, and comparing coefficients in $(1-2x+x^5)\,F(x)=1-x$ gives back the rule of Section 7. ^[7]

11. How fast the counts grow

A linear recurrence with constant coefficients has a standard solution: trying $T(n)=z^n$ in the rule of Section 5 gives the characteristic equation ^[9]

$$z^4=z^3+z^2+z+1.$$

Its roots, computed numerically, are $\rho\approx1.927562$, $r_2\approx-0.774804$ and the complex pair $r_{3,4}\approx-0.076379\pm0.814704\,i$ of absolute value about $0.818276$. They are distinct, so $T(n)$ is a combination of their $n$-th powers with coefficients fixed by the first values; ^[9] by the formula of Dresden and Du, shifted to our numbering, the coefficient of $r^n$ is $(r-1)/(5r-8)$. ^[10] For the large root it is

$$c=\frac{\rho-1}{5\rho-8}\approx0.566343,$$

and for the three small roots the coefficients have absolute values about $0.149470$, $0.144854$ and $0.144854$; the four coefficients themselves add up to $T(0)=1$. The powers of the small roots never grow, so $\bigl|T(n)-c\,\rho^n\bigr|$ is at most the sum of those three absolute values, about $0.43918$, which is less than $\tfrac12$: for every $n\ge0$, $T(n)$ is the whole number nearest to $c\,\rho^n$,

$$T(n)=\Bigl\lfloor c\,\rho^n+\tfrac12\Bigr\rfloor,$$

the rounding theorem of Dresden and Du for $k=4$. ^[10] For example $c\,\rho^5\approx15.0703$ and $c\,\rho^{10}\approx401.0172$; the error is at most $0.4392\cdot0.8183^n$. So the ratio of neighbouring counts tends to $\rho$, already $401/208\approx1.92788$, ^[7] and $T(n)$ has about $0.285\,n$ decimal digits, since $\log_{10}\rho\approx0.285$.

12. Pitfalls, limits and generalisations

The empty row. The table must start with $T(0)=1$; starting it with $0$ makes every entry $0$.
Loop order. A program whose outer loop runs over the tile sizes $s$ and whose inner loop over $n=s,s+1,\dots$ adds the entry for $n-s$ to the entry for $n$ counts each inventory of Section 8 only once, whatever the order of its tiles: the row of five gets $6$, not $15$.
Integer size. Section 3 gives $T(50)\le2^{49}$, so 64-bit integers are safe here. Exactly, $T(34)=2775641472$ is the first count above $2^{31}-1$, so signed 32-bit integers fail from $n=34$ on, and signed 64-bit integers from $n=68$ on.

For very long rows a matrix helps. Let $v_n$ be the column of the four latest counts $T(n)$, $T(n-1)$, $T(n-2)$, $T(n-3)$. Then $v_n=M\,v_{n-1}$ for $n\ge1$, with

$$M=\begin{pmatrix}1&1&1&1\\1&0&0&0\\0&1&0&0\\0&0&1&0\end{pmatrix},$$

because the first row adds the four counts, the rule of Section 5, and the other rows move them one place down. The column $v_0$ has the entries $1,0,0,0$, from $T(0)=1$ and the zeros before it, so $v_n=M^n v_0$ is the first column of $M^n$, and $T(n)$ is the top left entry of $M^n$. Exponentiation by squaring computes $M^n$ with at most $2\log_2n$ matrix products, ^[11] although for long rows these products work with numbers of about $0.285\,n$ digits.

How the Code Works

All three programs implement Sections 5 and 6 with a table dp in which dp[n] holds $T(n)$. In the C++ program ^[12] an Options structure holds the row length, $50$ by default, and a switch for the checkpoint. parse_arguments accepts --skip-checkpoints and --length= followed by digits, which parse_int_after_prefix converts; any other argument, an empty or negative length included, gives exit status 1.

solve(length) creates a std::vector of length + 1 zeros of type i64, the signed 64-bit std::int64_t, and sets dp[0] = 1, the empty row. For n from 1 to length the variable ways starts from dp[n - 1], the tilings ending with a grey square, and adds dp[n - 2], dp[n - 3] and dp[n - 4] for a red, green or blue last tile, each only if n is at least $2$, $3$ or $4$; these tests are the convention $T(m)=0$ for $m\lt0$. Each entry needs only smaller indices, so one pass fills the table, and as no term is negative, no partial sum in ways exceeds the final count. run_checkpoints compares solve(5) with the $15$ of the statement, a mismatch giving exit status 2; then main prints solve for the chosen length.

The Python program has no options: solve() fixes length = 50, fills the list dp with the same loop and tests, and prints dp[length]. The Java program does the same in main with an array of long. Only the integers differ: Python integers have unlimited precision, while std::int64_t and long have 64 bits, enough for every length up to $67$. Beyond that a Java long wraps around silently, and in C++ signed overflow is undefined behaviour.

Complexity and Verification

For a row of length $N$ the loop runs $N$ times with at most three additions each, so the time is $O(N)$: $144$ additions for $N=50$. The table holds $N+1$ numbers; four variables would suffice, as the bottom-up Fibonacci computation keeps only two. ^[4] For much longer rows the numbers themselves grow to about $0.285\,N$ digits ($T(100000)$ has $28501$), so with exact integers the table costs $O(N^2)$ digit operations and, if every entry is kept, $O(N^2)$ digits of memory. The listing of Section 4 needs time of at least $T(N)$, which grows exponentially.

The C++ program checks $T(5)=15$ on every run unless told to skip it. For this article these separate checks were run:

The C++, Python and Java programs print the same number for the row of fifty, and the C++ program with --length= reproduces the table of Section 6.
Listing every tiling one by one agrees with the table for every $n\le25$, and counting the cut patterns of Section 3 for every $n\le20$.
For every $n\le300$, including $50$, the inventory sum, the matrix power and the rounding formula, evaluated with $120$ significant digits, agree exactly with the table; so does the rule of Section 7 for $n\ge2$, and the bounds of Section 3 hold for $n\ge1$.
The rounding formula needs $c$ and $\rho$ to about as many digits as $T(n)$ has: with both rounded to six decimals, as in Section 11, and the formula then evaluated with high precision, it is first wrong at $n=22$, with ten decimals at $n=34$, and in double precision, about $16$ significant digits, already at $n=50$, $51$ or $52$, depending on the last bits of $c$ and $\rho$ and on how $\rho^n$ is computed.
The C++ program does not guard against overflow, and signed overflow is undefined behaviour in C++. From --length=68 on the sums leave the 64-bit range, and our builds printed a negative number; digit strings above $2^{31}-1$ overflow the loop of parse_int_after_prefix, so that --length=4294967301, which is $2^{32}+5$, printed $15$; and --length=2147483647 overflows length + 1 before the table is created.

Footnotes and References

The references supply the background facts; the two recurrences, the inventory sum, the generating function and the error bound of the rounding formula are derived above.

Project Euler 117 — Red, Green, and Blue Tiles. The official statement: a row is tiled with grey squares and oblong red (two units), green (three units) and blue (four units) tiles; a row of five units has exactly fifteen tilings, and the task asks for the number of tilings of a row of fifty units.
Project Euler 116 — Red, Green or Blue Tiles. The related problem with the same tiles, where colours may not be mixed and at least one coloured tile is used: a row of five has 7 tilings with red, 3 with green and 2 with blue tiles.
Wikipedia — Composition (combinatorics). For n ≥ 1 there are 2^(n−1) compositions of n, ordered sums of positive integers, since each of the n − 1 places between n ones gets a plus sign or a comma.
Wikipedia — Dynamic programming. For the Fibonacci numbers, naive recursion takes exponential time, while memoization and the bottom-up method take O(n) time, the latter with constant space.
OEIS A000078 — Tetranacci numbers. 0, 0, 0, 1, 1, 2, 4, 8, 15, 29, …; a(n) counts the compositions of n − 3 with no part greater than 4, and a(n) = 2a(n−1) − a(n−5) for n ≥ 5, so T(n) = a(n + 3).
Wikipedia — Multinomial theorem. The coefficients of (x₁ + ⋯ + xₘ)ⁿ are the multinomial coefficients n!/(k₁!⋯kₘ!), which also count the distinct arrangements of a multiset.
Wikipedia — Generalizations of Fibonacci numbers. Each tetranacci number is the sum of the four preceding ones, and the ratio of adjacent terms tends to 1.927561975…, the positive root of x⁴ − x³ − x² − x − 1; the k-nacci generating function has the denominator 1 − x − … − xᵏ, or 1 − 2x + xᵏ⁺¹ in a second form.
Wikipedia — Generating function. A sequence becomes the coefficients of a formal power series; 1/(1 − x) = 1 + x + x² + … is the geometric series, and the series is rational exactly when the sequence satisfies a linear recurrence with constant coefficients.
Wikipedia — Linear recurrence with constant coefficients. When the roots of the characteristic polynomial are distinct, every solution is a linear combination of their powers, with coefficients fitted to the initial values.
G. P. B. Dresden and Z. Du — A Simplified Binet Formula for k-Generalized Fibonacci Numbers, Journal of Integer Sequences 17 (2014), Article 14.4.7. Theorem 1 writes F⁽ᵏ⁾ₙ, with F⁽ᵏ⁾₁ = 1 and zeros before, as the sum of (α − 1)/(2 + (k + 1)(α − 2)) · αⁿ⁻¹ over the roots α of xᵏ − xᵏ⁻¹ − … − 1; by Theorem 2, rounding the term of the positive root gives F⁽ᵏ⁾ₙ for all n ≥ 2 − k. Here T(n) = F⁽⁴⁾ₙ₊₁.
Wikipedia — Exponentiation by squaring. A power xⁿ needs ⌊log₂ n⌋ squarings and at most as many further multiplications; the method is often used for powers of matrices.
C++ — Euler117.cpp. The immutable revision described above, with parse_arguments, solve, run_checkpoints and the options --length= and --skip-checkpoints.

Problem 117 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using i64 = std::int64_t;

struct Options {
    int length = 50;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--length=", options.length)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.length >= 0;
}

i64 solve(const int length) {
    std::vector<i64> dp(static_cast<std::size_t>(length + 1), 0);
    dp[0] = 1;

    for (int n = 1; n <= length; ++n) {
        i64 ways = dp[static_cast<std::size_t>(n - 1)];
        if (n >= 2) {
            ways += dp[static_cast<std::size_t>(n - 2)];
        }
        if (n >= 3) {
            ways += dp[static_cast<std::size_t>(n - 3)];
        }
        if (n >= 4) {
            ways += dp[static_cast<std::size_t>(n - 4)];
        }
        dp[static_cast<std::size_t>(n)] = ways;
    }

    return dp[static_cast<std::size_t>(length)];
}

bool run_checkpoints() {
    if (solve(5) != 15) {
        std::cerr << "Checkpoint failed for length=5" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.length) << '\n';
    return 0;
}

Python

# Problem 117: Red, green, and blue tiles
# Replace with tiles of sizes 2,3,4 (mixing allowed).

def solve():
    length = 50
    dp = [0] * (length + 1)
    dp[0] = 1
    for n in range(1, length + 1):
        dp[n] = dp[n - 1]
        if n >= 2: dp[n] += dp[n - 2]
        if n >= 3: dp[n] += dp[n - 3]
        if n >= 4: dp[n] += dp[n - 4]
    print(dp[length])

solve()

Java

public class Euler117 {
    public static void main(String[] args) {
        int len=50; long[] dp=new long[len+1]; dp[0]=1;
        for(int n=1;n<=len;n++){dp[n]=dp[n-1];if(n>=2)dp[n]+=dp[n-2];if(n>=3)dp[n]+=dp[n-3];if(n>=4)dp[n]+=dp[n-4];}
        System.out.println(dp[len]);
    }
}