Double array dynamic programming

The double array dynamic programming is a dynamic programming algorithm that uses two arrays to store the intermediate results.

A common example is the robber house problem. You can always see some "robber" who is not willing to rob two adjacent houses or some other strange conditions. Then you need to store the optimal solution for both actions, rob and not rob.

In such cases, using two arrays to store the intermediate results is a good idea.

More generally, two-dimensional dynamic programming shows up whenever the optimal structure depends on two independent indices — typically a pair of positions in two sequences, or a position paired with a capacity/mode. A canonical example is the longest common subsequence (LCS): given two strings s1 and s2, find the length of the longest sequence that appears in both as a subsequence (not necessarily contiguous).

Define dp[i][j] as the LCS length of the prefixes s1[:i] and s2[:j]. The recurrence is

• dp[0][j] = dp[i][0] = 0 for all i, j (empty prefix),
• if s1[i-1] equals s2[j-1] then dp[i][j] = dp[i-1][j-1] + 1,
• otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

The answer is dp[len(s1)][len(s2)]. The table is filled row by row, and each cell is computed in constant time from three already-filled neighbors, yielding the $O(m n)$ bound below.

Codes

Python

House-robber style double-array DP:

def robber(nums: List[int]) -> int:
    n=len(nums)
    if n==0:
        return 0
    if n==1:
        return nums[0]
    dp=[0]*n
    dp[0]=nums[0]
    dp[1]=max(nums[0],nums[1])
    for i in range(2,n):
        dp[i]=max(dp[i-1],dp[i-2]+nums[i])
    return dp[n-1]

LCS length with a full 2D table:

def solve(xs):
    """xs is [s1, s2]; return the length of the longest common subsequence."""
    s1, s2 = xs
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

C++

#include <algorithm>
#include <string>
#include <vector>

int lcs_length(const std::string& s1, const std::string& s2) {
    int m = static_cast<int>(s1.size());
    int n = static_cast<int>(s2.size());
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

Example

Loading Python runner...

Description

Run time analysis

$O(m n)$, where m and n are the lengths of the two strings. Every cell of the (m+1) by (n+1) table is computed exactly once, and each cell does constant work (one comparison and one max of three known cells).

Space analysis

$O(m n)$ for the full table. This can be reduced to $O(\min(m, n))$ by keeping only the previous row, because the recurrence only references dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]; the reduction is a standard rolling array optimization and does not change the answer.

Proof of correctness

We prove by induction on (i, j) in lexicographic order that dp[i][j] equals the length of the longest common subsequence of s1[:i] and s2[:j].

Base case: dp[0][j] = dp[i][0] = 0, because at least one of the two prefixes is empty and the empty subsequence is the only common subsequence.

Inductive step: assume the claim holds for all pairs (i', j') that are lexicographically smaller than (i, j). Let L be the true LCS length of s1[:i] and s2[:j].

Case A (s1[i-1] equals s2[j-1]): any optimal LCS either uses this matched character or not. If it does, removing it gives an LCS of s1[:i-1] and s2[:j-1] of length L - 1, so by induction L - 1 is less than or equal to dp[i-1][j-1], hence L is less than or equal to dp[i-1][j-1] + 1. If it does not, then L equals the LCS of s1[:i-1] and s2[:j] or of s1[:i] and s2[:j-1], which by induction is at most max(dp[i-1][j], dp[i][j-1]), and that is at most dp[i-1][j-1] + 1 because extending by one matched character can only increase the LCS by one. Conversely, we can achieve dp[i-1][j-1] + 1 by appending the matched character to an optimal LCS of the shorter prefixes, so L equals dp[i-1][j-1] + 1.

Case B (s1[i-1] does not equal s2[j-1]): an optimal LCS of s1[:i] and s2[:j] cannot end with both characters simultaneously, so it is an LCS of either s1[:i-1] and s2[:j] or s1[:i] and s2[:j-1]. By induction this maximum equals max(dp[i-1][j], dp[i][j-1]) and that value is achievable.

In both cases dp[i][j] = L, completing the induction. The final answer is dp[m][n].

Extensions

Applications

Leetcode 1320

• Leetcode 1320

Intuition

The key idea is to use two arrays to track finger.

Solution

class Solution:
    def minimumDistance(self, word: str) -> int:
        board=[
            [0,1,2,3,4,5],
            [6,7,8,9,10,11],
            [12,13,14,15,16,17],
            [18,19,20,21,22,23],
            [24,25]
        ]
        d=[[0]*26 for _ in range(26)]
        for y1 in range(5):
            for x1 in range(6):
                if y1==4 and x1>1:
                    break
                for y2 in range(5):
                    for x2 in range(6):
                        if y2==4 and x2>1:
                            break
                        d[board[y1][x1]][board[y2][x2]]=abs(y1-y2)+abs(x1-x2)
        c=[ord(i)-ord('A') for i in word]
        @lru_cache(None)
        def dp(i,a,b):
            if i==len(c):
                return 0
            # move left
            if a>-1:
                res=dp(i+1,c[i],b)+d[a][c[i]]
            else:
                res=dp(i+1,c[i],b)
            # move right
            if b>-1:
                res=min(res,dp(i+1,a,c[i])+d[b][c[i]])
            else:
                res=min(res,dp(i+1,a,c[i]))
            return res
        return dp(0,-1,-1)

Leetcode 3186

• Leetcode 3186

Intuition

The key idea is to use two arrays to store the intermediate results. We can use counter to compress the total possible states of the spells and use bisect to find the index of the spell that is compatible with the current spell.

Solution

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        # 2dp
        pc=Counter(power)
        sel=sorted(list(pc.keys()))
        dp=[[k*pc[k],0] for k in sel]
        n=len(sel)
        for i in range(1,n):
            # find the index of the spell that is compatible with the current spell
            loi=bisect.bisect_left(sel,sel[i]-2)-1
            if(sel[loi]<sel[i]-2): 
                # if the compatible spell is found, add the damage of the compatible spell to the current spell
                dp[i][0]+=max(dp[loi])
            # add the damage of the previous spell to the current spell
            dp[i][1]+=max(dp[i-1])
        return max(dp[-1])

References

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