Dynamic Programming: Or What You Do If You Can’t Jump Like Mario, and Some Thoughts on Translating Mathematical Statements into Code

If you’re Mario, you can always just jump to the end of something. The rest of us? Unlikely.

We all know by now that mathematics, computer science, and programming are closely related, but different. There’s a huge overlap, but there are differences between the fields. A big, and notable, intersection between all three is dynamic programming.

• Mathematics: In math, you can loosely define dynamic programming as a method for optimizing the solution of problems that can be defined recursively.
• Computer science: Optimal algorithms for particular tasks; specifically the trade-off between time and space, where time is more valuable than space. In a lot of cases, a naive solution can have a time complexity of O(n²) or worse, but DP can bring this to O(n) while adding an “affordable” space cost of O(n). Sometimes that space cost may even be O(1) — specifically, the problem can be solved without needing to store every intermediate result.
• Programming: The realization of those algorithms in code.

This came to my mind as a result of two things: solving the Advent of Code problems in Haskell, and LeetCode programming problems. Specifically, I saw that I was wrestling with dynamic programming problems on LC more than I expected to, and got to thinking about that. Obviously, writing Haskell is a lot more similar to “pure” mathematics than the languages LC uses, or the ones you’re going to see used in the lion’s share of programming interviews, especially in machine learning.

Identifying and Defining the Problem

Since I identified a weak point, and one I didn’t expect to have, I did the most reasonable thing, which was start working on it, first by reviewing the concepts and then solving a bunch of dynamic programming problems. I started with reviewing a YouTube video that my friend and mentor James Powell made on it, which you can find here:

Here’s a quick tl;dr on that video:

1. Pretty much every DP problem can be solved in a fairly rote, formulaic way.
2. That way begins by defining what needs to be optimized, i.e. a function like opt(n) . You can start with that by usingan informal definition.
3. With that initial definition, you can articulate what the intermediate steps are.
4. With an idea of the shape of those intermediate steps, you can define the base cases for the DP problem, just like any other domain where you’re going to utilize a recursive solution.
5. The recursive solution is likely to be either bottom-up or top-down. With a “bottom-up”, your solution’s iterations would begin with those base cases, building up from them, and with a “top-down” one, they would grow down to the base cases. In the “top-down” formulation, you of course want to be mindful to make sure your solution will always eventually terminate and not recurse forever.
6. In Python specifically, you could either explicitly memoize it using the @functools.cache decorator, or explicitly track the intermediate results (usually either a one- or two-dimensional array, or a more explicit mapping type like a dict / defaultdict).

Using the Definition

Now here’s how I applied that to the LC problem “Jump Game II”. Here’s a short definition of the problem, in my own words:

You’re given an array nums, where nums[i] is how many indices forward you can advance (or “how far you can jump,” because people on LC aren’t Mario and their maximum jumps are defined by a table rather than the sort of athleticism that only a plumber from Brooklyn, New York possesses). The array’s values are such that you will be able to reach the end (last index) from the start (index zero). Find the minimum number of “jumps” to do this in.

1. Define what needs to be optimized: I made a rough definition of the function like this (taken directly from some scratch paper): opt(nums) = min. jumps to get from nums[0] -> nums[len(nums)-1] .
2. Refine the initial definition: For me, a refinement of my opt function was opt(nums, x) = number of ways you can get from nums[x] to nums[len(nums)-1].
3. Define the base cases: The base case here is if you’re at the end, or in other words, opt(nums, x) where x == len(nums). If you’re at the end, you don’t need to take any steps, you’re done. So that case is 0. Languages like Haskell and OCaml provide a very nice “math textbook”-looking way to define this case, but even if you’re not using them, it’s usually pretty simple conditional. I identified another base/terminating case, which is where nums[x] == 0 (so you can’t reach the end from that index), but that’s fairly easy to handle in an implementation.
4. Define the general case and how it recurses into the base case eventually: Here, the general recursive case is pretty simple to define in either plain English (opt(nums, x) = 1 + the minimum of any of the steps you can reach from x, which is {1, …, nums[x]}) or a more mathematical way (1 + min(nums[x+i]), ∀ i ∈ {1, …, min(nums[x], len(nums))}), but is just a bit tricky to implement.
5. Determine how to implement it: since we’re working with Python lists here, a famously unhashable type, the functools.cache decorator will not work. In a real “production” solution to this sort of problem, we could explicitly accept tuples at the start, or the interface to our program/library/what have you. But I felt like respecting what I considered to be the spirit of the problem.

Actualizing the Mathematics

With all that said, here is my solution, removed from LC’s class Solution harness:

def jump(self, nums: List[int]) -> int:
    if len(nums) == 1:
        return 0
    elif len(nums) == 2:
        return 1
    inf = 1_000_000
    dp = [inf for _ in nums]
    dp[-1] = 0
    for i in range(len(dp)-2, -1, -1):
        if nums[i] != 0:
            # If the end of `nums` is within `i` steps maximum,
            # we already know that dp[i] should be 1. 
            if nums[i] + i >= len(nums):
                dp[i] = 1
            else:
                dp[i] = 1 + min(dp[i+1:i+nums[i]+1])
    return dp[0]

Some Last Thoughts

A couple thoughts on how I did this:

1. We could special-case setting the last index to 0 in the loop: if i == len(dp)-1, and change the range we iterate over correspondingly, but I felt that defining it outside made more sense: closer to the creation of our dynamic programming array, and to quote the Zen of Python, explicit is better than implicit.
2. Defining our inf like this is sort of kludgey, and I set it based on an assumption about the problem. Doing something like setting it to INTMAX in a language with bounded integral types would also make sense. A language like Haskell or OCaml would allow you to easily define a type for this, and in Haskell at least there’s minimal overhead from defining new data types, which is something I like a lot about the language. That type could look something like data Intermediate = Unknown | Known Int, and we would start with an array of Unknown and flip them all into Knowns as we work backward. If you know a little about Haskell, you’ll realize that this type is spiritually basically the Maybe type/monad, which is neat.
3. On the other hand, Python or general imperative-style memoization is a little (but not a lot, things like the State monad or monad transformers look far scarier than they actually are:) ) funkier to get into a Haskell program, and Haskell lists are linked lists, which don’t really scale for any “real” input size. I believe OCaml would handle this better since it’s pretty trivial to jump into a more mutable or imperative style of programming in OCaml, but my OCaml experience is basically zero.

It wouldn’t be very complicated to implement a solution to this problem in Haskell, but without the full test set easily available on hand, it’s not as interesting or rewarding. I may do it in the future anyway.

Addressing your weak points like this is honestly pretty fun and energizing if you can do it in a methodical way and tie it in with other things you work on or are interested in. Happy coding, and Happy New Year!