[triska]

I often use the declarative programming language Prolog to solve dynamic programming tasks, because it is easy to type and helps you to declaratively express what a solution looks like. After you have expressed what must be the case in a solution, you can easily enable memoization on top of the existing code.

For example, here is how you can use Prolog to solve the task from the article. The following Prolog predicate is true iff a given runway (represented as a list of "t" and "f" elements) is safe with a given speed:

    :- use_module(library(clpfd)).

    safe_runway(0, [t|_]).
    safe_runway(Speed0, Rs) :-
            Speed0 #> 0,
            Rs = [t|_],
            (   Speed = Speed0
            ;   Speed #= Speed0 - 1
            ;   Speed #= Speed0 + 1
            ),
            length(Prefix, Speed),
            append(Prefix, Rest, Rs),
            safe_runway(Speed, Rest).

Sample query and answer:

    ?- safe_runway(4, [t,f,t,t,t,f,t,t,f,t,t]).
    true .

One interesting aspect of this solution is that we can generalize this query, and also use the same program to answer the question: Which speeds are actually safe for a given runway?

For example:

    ?- safe_runway(Speed, [t,f,t,t,t,f,t,t,f,t,t]).
    Speed = 0 ;
    Speed = 2 ;
    etc.

To enable memoization for this task, you only have to use your Prolog system's tabling mechanism. For example, in SWI-Prolog, you turn this into a dynamic programming solution by adding the directive

    :- table safe_runway/2.

This makes the Prolog engine automatically remember and recall solutions it has already computed.