1D Dynamic Programming

The 1D dynamic programming is a dynamic programming algorithm that uses a single array to store the intermediate results, where the final solution may depend on the previous states.

A classical example is the fibonacci sequence, even though it can be solved using algebraic equations, it is a good example to show the power of dynamic programming.

This kinds of linear recurrent relations is also widely studied in the field of combinatorics. Some linear recurrent relations can be solved using algebraic equations, but some cannot, this will be the case where dynamic programming is the "only" way to solve it. (perhaps)

Another canonical one-dimensional DP problem is the longest increasing subsequence (LIS): given an array of integers, find the length of the longest strictly increasing subsequence.

A naive DP defines dp[i] as the length of the longest increasing subsequence ending at position i and takes $O(n^2)$ time. The classic $O(n \log n)$ improvement is patience sorting: sweep left to right and maintain a list tails where tails[k] is the smallest possible tail value among all increasing subsequences of length k+1 seen so far. For each incoming value x we replace the leftmost tail that is greater than or equal to x, or append x if no such tail exists. The answer is the final length of tails. The list itself is not necessarily a valid LIS, but its length is.

Binary search (bisect_left) drops the per-element work from linear to logarithmic, yielding the $O(n \log n)$ bound below.

Codes

Python

Fibonacci-style 1D DP:

def dp(n: int) -> int:
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(1,n+1):
        dp[i]=dp[i-1]+dp[i-2]
    return dp[n]

Patience-sorting LIS in $O(n \log n)$:

from bisect import bisect_left

def solve(xs):
    """Return the length of the longest strictly increasing subsequence of xs."""
    tails = []
    for x in xs:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

C++

#include <algorithm>
#include <vector>

int lis_length(const std::vector<int>& xs) {
    std::vector<int> tails;
    for (int x : xs) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    return static_cast<int>(tails.size());
}

Example

Loading Python runner...

Description

Run time analysis

$O(n \log n)$. The outer loop runs $n$ times, and each iteration performs a binary search over the tails array (whose length never exceeds $n$) in $O(\log n)$ time. The constant-time update at the found position does not change the bound.

Space analysis

$O(n)$. The tails buffer can grow up to the length of the longest increasing subsequence in the worst case, which is $n$. No other auxiliary storage is needed.

Proof of correctness

Let L be the true LIS length of the input. We prove by induction on the number of elements processed that the following invariant holds after each step:

• tails has length equal to the current best LIS length on the prefix.
• For every k in range, tails[k] is the minimum possible tail value of any increasing subsequence of length k+1 in the prefix.
• tails is strictly increasing.

Base case: before any element is seen, tails is empty and the invariant holds vacuously.

Inductive step: assume the invariant holds after processing the first i elements, and consider element x. Let i = bisect_left(tails, x).

Case 1 (i equals the current length): every existing tail is strictly less than x, so appending x extends every length-k subsequence whose tail is tails[k-1] into a length-(k+1) subsequence ending at x. This strictly improves the best length by one and x becomes the new minimum tail for that length because no previous length-(k+1) sequence existed.

Case 2 (i is less than the current length): tails[i] is the smallest length-(i+1) tail and tails[i] is greater than or equal to x. Replacing tails[i] with x preserves strict monotonicity (tails[i-1] is strictly less than x by the definition of bisect_left and tails[i+1] is strictly greater than tails[i] which is greater than or equal to x, hence strictly greater than x). Any subsequence of length i+1 that ends at tails[i] can be replaced (in terms of tail value) by the subsequence formed by taking a length-i subsequence with tail strictly less than x (which exists by the invariant on tails[i-1]) and appending x. So the new tails[i] remains the minimum length-(i+1) tail.

By induction the invariant holds after processing every element, so the final length of tails equals L.

Extensions

Applications

Leetcode 3494

• Leetcode 3494

Intuition

This problem is particularly tricky because you are required to use backtracking to find the minimum amount of time to brew the potions for each round.

Combined with the reversed dp order, it takes me a few hours to figure out the solution.

Solution

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n,m=len(skill),len(mana)
        init=[0]*(n+1)
        for i in range(m):
            for j in range(n):
                init[j+1]=max(init[j+1],init[j])+skill[j]*mana[i]
            for j in range(n-1,0,-1):
                init[j]=init[j+1]-skill[j]*mana[i]
        return init[-1]

References

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3rd ed., Chapter 15 (Dynamic Programming).
• cp-algorithms — Longest increasing subsequence