How to Design Transition Equations

Perhaps some readers have read the previous article Dynamic Programming Detailed Explanation and learned the routine of dynamic programming: identifying the "state" of the problem, clarifying the meaning of the dp array/function, and defining the base case. However, they might not know how to determine the "choices," meaning they can't find the state transition relationship and still can't write a dynamic programming solution. What should they do?

Don't worry. The difficulty of dynamic programming lies in finding the correct state transition equation. This article will use the classic "Longest Increasing Subsequence Problem" to explain the general technique for designing dynamic programming: mathematical induction.

The Longest Increasing Subsequence (LIS) is a very classic algorithm problem. The dynamic programming solution is relatively easy to think of, with a time complexity of O(N^2). We will use this problem to explain step by step how to find the state transition equation and how to write a dynamic programming solution. A less intuitive approach is to use binary search, which has a time complexity of O(NlogN). We will use a simple card game to help understand this clever solution.

LeetCode problem 300 "Longest Increasing Subsequence" is exactly this problem:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Input: nums = [0,1,0,3,2,3]
Output: 4

Input: nums = [7,7,7,7,7,7,7]
Output: 1

// Function signature
int lengthOfLIS(int[] nums);

// function signature
int lengthOfLIS(vector<int>& nums);

# Function signature
def lengthOfLIS(nums: List[int]) -> int:

// function signature
func lengthOfLIS(nums []int) int {}

// Function signature
var lengthOfLIS = function(nums) {}

For example, given the input nums=[10,9,2,5,3,7,101,18], the longest increasing subsequence is [2,3,7,101], so the output of the algorithm should be 4.

Note the difference between the terms "subsequence" and "substring." A substring must be contiguous, while a subsequence does not have to be. Let's design a dynamic programming algorithm to solve this problem.

1. Dynamic Programming Approach

The core design philosophy of dynamic programming is mathematical induction.

Most people are familiar with mathematical induction from high school, and the concept is straightforward. For example, if we want to prove a mathematical statement, we first assume the statement is true for k < n, then use this assumption to prove it is also true for k = n. If we can prove this, it means the statement is true for any k.

Similarly, when designing a dynamic programming algorithm, don't we need a dp array? We can assume that dp[0...i-1] has already been computed and then ask ourselves: how can we use these results to compute dp[i]?

Let's use the problem of finding the longest increasing subsequence as an example. But first, we need to clearly define the meaning of the dp array, specifically what the value of dp[i] represents.

Our definition is as follows: dp[i] represents the length of the longest increasing subsequence that ends with the number nums[i].

Based on this definition, we can establish the base case: the initial value of dp[i] is 1 because the longest increasing subsequence ending with nums[i] must at least include itself.

Here are two examples:

This GIF demonstrates the evolution of the algorithm:

Based on this definition, our final result (the maximum length of the subsequence) should be the maximum value in the dp array.

int res = 0;
for (int i = 0; i < dp.length; i++) {
    res = Math.max(res, dp[i]);
}
return res;

Readers might wonder, in the earlier algorithm progression, each result of dp[i] was observed with the naked eye. How should we design the algorithm logic to correctly compute each dp[i]?

This is the essence of dynamic programming: how to design the algorithm logic for state transitions to ensure correct execution. Here, we need to use the concept of mathematical induction:

Assuming we already know all the results of dp[0..4], how can we derive dp[5] from these known results?

Based on our previous definition of the dp array, we now want to find the value of dp[5], which means we want the longest increasing subsequence ending with nums[5].

nums[5] = 3. Since it is an increasing subsequence, we just need to find the subsequences ending with elements smaller than 3, and then append 3 to the end of these subsequences to form a new increasing subsequence. The length of this new subsequence will increase by one.

Which elements before nums[5] are smaller than nums[5]? This is straightforward to calculate; a for loop can be used to compare and find these elements.

What is the length of the longest increasing subsequence ending with these elements? Let's recall our definition of the dp array, which records the length of the longest increasing subsequence ending with each element.

In our example, nums[0] and nums[4] are both smaller than nums[5]. By comparing the values of dp[0] and dp[4], we combine nums[5] with the longer increasing subsequence to get dp[5] = 3:

for (int j = 0; j < i; j++) {
    if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
    }
}

When i = 5, this code logic can calculate dp[5]. In fact, at this point, we have basically solved this algorithm problem.

Readers might wonder, we just calculated dp[5], how do we calculate dp[4], dp[3], and others? Similar to mathematical induction, once you can calculate dp[5], you can calculate the rest:

for (int i = 0; i < nums.length; i++) {
    for (int j = 0; j < i; j++) {
        // find elements in nums[0..i-1] that are smaller than nums[i]
        if (nums[i] > nums[j]) {
            // append nums[i] to the end, forming a subsequence of length dp[j] + 1,
            // and it is an increasing subsequence ending with nums[i]
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}

Combining the base case we just discussed, let's take a look at the complete code:

class Solution {
    public int lengthOfLIS(int[] nums) {
        // Definition: dp[i] represents the length of
        // the longest increasing subsequence ending with
        int[] dp = new int[nums.length];
        // base case: initialize all elements of dp array to 1
        Arrays.fill(dp, 1);
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);

                }
            }
        }
        
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // Definition: dp[i] represents the length of
        // the longest increasing subsequence ending with
        vector<int> dp(nums.size());
        // base case: initialize all elements of dp array to 1
        fill(dp.begin(), dp.end(), 1);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);

                }
            }
        }
        
        int res = 0;
        for (int i = 0; i < dp.size(); i++) {
            res = max(res, dp[i]);
        }
        return res;
    }
};

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # Definition: dp[i] represents the length of
        # the longest increasing subsequence ending with
        dp = [1]*len(nums)
        # base case: initialize all elements of dp array to 1
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]: 
                    dp[i] = max(dp[i], dp[j] + 1) 

        
        res = 0
        for i in range(len(dp)):
            res = max(res, dp[i])
        return res

func lengthOfLIS(nums []int) int {
    // Definition: dp[i] represents the length of the
    // longest increasing subsequence ending with
    dp := make([]int, len(nums))
    // base case: initialize all elements of dp array to 1
    for i := range dp {
        dp[i] = 1
    }
    for i := 0; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                // dp[i] = Math.max(dp[i], dp[j] + 1);
                dp[i] = max(dp[i], dp[j] + 1);

            }
        }
    }

    res := 0
    for i := 0; i < len(dp); i++ {
        res = max(res, dp[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

var lengthOfLIS = function(nums) {
    // Definition: dp[i] represents the length of the
    // longest increasing subsequence ending with
    let dp = new Array(nums.length).fill(1);
    // base case: initialize all elements of the dp array to 1
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);

            }
        }
    }

    let res = 0;
    for (let i = 0; i < dp.length; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
};

At this point, the problem is solved with a time complexity of $O(N^2)$. Here is a summary of how to determine the state transition relation in dynamic programming:

1. Clearly define the dp array. This step is crucial for any dynamic programming problem. If the definition is inappropriate or unclear, it can hinder subsequent steps.

2. Based on the definition of the dp array, use the principle of mathematical induction. Assume dp[0...i-1] is known, and find a way to determine dp[i]. Once this step is completed, the problem is essentially solved.

However, if this step cannot be completed, it may indicate that the definition of the dp array is not appropriate and needs redefining. Alternatively, it might mean that the information stored in the dp array is insufficient to deduce the next answer, necessitating an expansion of the dp array into a two-dimensional or even three-dimensional array.

The current solution follows the standard dynamic programming approach, but for the longest increasing subsequence problem, this method may not be optimal and might not pass all test cases. A more efficient solution will be discussed below.

2. Binary Search Approach

This solution has a time complexity of $O(NlogN)$. To be honest, it's not a method that most people would think of (though perhaps those who have played certain card games might come up with it). It's good to be aware of it, but in most cases, providing a dynamic programming solution is already quite commendable.

Based on the problem's description, it is hard to imagine how this issue could be related to binary search. In fact, the longest increasing subsequence problem is related to a card game known as patience game. There is even a sorting method called patience sorting.

For simplicity, we will skip all mathematical proofs and use a simplified example to understand the algorithm's concept.

First, imagine you have a row of playing cards. We process these cards one by one from left to right, just like traversing an array, and ultimately divide them into several piles.

The following rules must be followed when handling these playing cards:

You can only place a card with a smaller number on top of a card with a larger number. If the current card's number is larger and there is no suitable pile to place it, create a new pile and place the card there. If there are multiple piles to choose from, place the card on the leftmost pile.

For example, the cards mentioned above will eventually be divided into 5 piles (we consider card A to be the largest and card 2 to be the smallest).

Why should you place the card on the leftmost pile when there are multiple options? This ensures that the top cards of the piles are in order (2, 4, 7, 8, Q), proof omitted.

By following the rules above, you can calculate the longest increasing subsequence. The number of piles corresponds to the length of the longest increasing subsequence, proof omitted.

We just need to program the process of handling the playing cards. Each time you handle a card, you need to find a suitable pile top to place it on. Since the pile tops are ordered, binary search can be used: use binary search to find the position to place the current card.

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] top = new int[nums.length];
        // initialize the number of piles to 0
        int piles = 0;
        for (int i = 0; i < nums.length; i++) {
            // the poker card to be processed
            int poker = nums[i];

            // ***** binary search for the left boundary *****
            int left = 0, right = piles;
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            // *********************************
            
            // no suitable pile found, create a new pile
            if (left == piles) piles++;
            // place this card on the top of the pile
            top[left] = poker;
        }
        // the number of piles is the length of LIS
        return piles;
    }
}

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> top(nums.size());
        // initialize the number of piles to 0
        int piles = 0;
        for (int i = 0; i < nums.size(); i++) {
            // the card to be processed
            int poker = nums[i];

            // ***** binary search for the left boundary *****
            int left = 0, right = piles;
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            // ********************************
            
            // no suitable pile found, create a new one
            if (left == piles) piles++;
            // place this card on the top of the pile
            top[left] = poker;
        }
        // the number of piles is the length of LIS
        return piles;
    }
};

class Solution:
    def lengthOfLIS(self, nums):
        top = [0] * len(nums)
        # initialize the number of piles to 0
        piles = 0
        for i in range(len(nums)):
            # the poker card to be processed
            poker = nums[i]

            # binary search for the left boundary
            left, right = 0, piles
            while left < right:
                mid = (left + right) // 2
                if top[mid] > poker:
                    right = mid
                elif top[mid] < poker:
                    left = mid + 1
                else:
                    right = mid

            # no suitable pile found, create a new one
            if left == piles:
                piles += 1
            # place this card on top of the pile
            top[left] = poker
        # the number of piles is the length of LIS
        return piles

func lengthOfLIS(nums []int) int {
    top := make([]int, len(nums))
    // initialize the number of piles to 0
    var piles int
    for i := 0; i < len(nums); i++ {
        // the poker card to be processed
        poker := nums[i]

        // ***** binary search for the left boundary *****
        var left, right int = 0, piles
        for left < right {
            mid := (left + right) / 2
            if top[mid] > poker {
                right = mid
            } else if top[mid] < poker {
                left = mid + 1
            } else {
                right = mid
            }
        }
        // ********************************
        
        // no suitable pile found, create a new one
        if left == piles {
            piles++
        }
        // place this card on the top of the pile
        top[left] = poker
    }
    // the number of piles is the length of LIS
    return piles
}

var lengthOfLIS = function(nums) {
    var top = new Array(nums.length);
    // initialize the number of piles to 0
    var piles = 0;
    for (var i = 0; i < nums.length; i++) {
        // the poker card to be processed
        var poker = nums[i];

        // ***** binary search for the left boundary *****
        var left = 0, right = piles;
        while (left < right) {
            var mid = Math.floor((left + right) / 2);
            if (top[mid] > poker) {
                right = mid;
            } else if (top[mid] < poker) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // ********************************
        
        // no suitable pile found, create a new one
        if (left == piles) piles++;
        // place this card on the top of the pile
        top[left] = poker;
    }
    // the number of piles is the length of LIS
    return piles;
};

Here, the explanation of the binary search solution is complete.

This solution is indeed hard to come up with. First, it involves mathematical proof. Who would think that following these rules would yield the longest increasing subsequence? Second, it requires the application of binary search. If you're not clear on the details of binary search, even with the idea, it's hard to implement correctly.

Therefore, consider this method as a mental exercise. However, the design approach of dynamic programming should be fully understood: assume the previous answers are known, use mathematical induction to correctly deduce and transition states, and ultimately arrive at the solution.

3. Extension to Two Dimensions

Let's look at an interesting problem often encountered in real life, LeetCode Problem 354 "Russian Doll Envelopes". Here is the problem statement:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

This problem is actually a variant of the longest increasing subsequence (LIS), as each valid nesting involves placing a larger envelope over a smaller one. Essentially, it is about finding the longest increasing subsequence on a two-dimensional plane, where the length represents the maximum number of envelopes that can be nested.

The standard LIS algorithm is designed to find the longest subsequence in a one-dimensional array, but our envelopes are represented by two-dimensional pairs like (w, h). How can we apply the LIS algorithm in this context?

Readers might think of calculating the area using w × h and then applying the standard LIS algorithm on the areas. However, upon closer consideration, this approach fails. For example, 1 × 10 is greater than 3 × 3, but clearly, these two envelopes cannot nest within each other.

The solution to this problem is quite ingenious:

First, sort the widths w in ascending order. If there are ties in w, then sort the heights h in descending order. After that, treat all h as an array and calculate the length of the Longest Increasing Subsequence (LIS) on this array, which will be the answer.

To better understand, let's visualize it by first sorting these pairs:

Then, find the Longest Increasing Subsequence on the h values. This subsequence represents the optimal nesting scheme:

Why does this approach find the sequence of envelopes that can be nested within each other? A bit of thought will make it clear:

Firstly, sorting the widths w in ascending order ensures that the w dimension can be nested. Thus, we only need to focus on the h dimension being able to nest.

Secondly, envelopes with the same width w cannot contain each other. Therefore, for envelopes with the same width w, we sort the heights h in descending order to ensure that there are no multiple envelopes with the same w in the two-dimensional LIS (as the problem states that identical dimensions cannot be nested).

Here is the code for the solution:

class Solution {
    // envelopes = [[w, h], [w, h]...]
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        // sort by width in ascending order, if widths
        // are the same, sort by height in descending
        Arrays.sort(envelopes, (int[] a, int[] b) -> {
            return a[0] == b[0] ? 
                b[1] - a[1] : a[0] - b[0];
        });
        // find the LIS for the height array
        int[] height = new int[n];
        for (int i = 0; i < n; i++)
            height[i] = envelopes[i][1];

        return lengthOfLIS(height);
    }

    int lengthOfLIS(int[] nums) {
        // see previous text
    }
}

class Solution {
public:
    // envelopes = {{w, h}, {w, h}...}
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        // sort by width in ascending order, if widths
        // are the same, sort by height in descending
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>& b) {
            return a[0] == b[0] ? 
                b[1] < a[1] : a[0] < b[0];
        });
        // find the LIS for the height array
        vector<int> height(n);
        for (int i = 0; i < n; i++)
            height[i] = envelopes[i][1];

        return lengthOfLIS(height);
    }

    int lengthOfLIS(vector<int>& nums) {
        // see previous text
    }
};

class Solution:
    # envelopes = [[w, h], [w, h]...]
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        # sort by width in ascending order, if
        # widths are the same, sort by height in
        envelopes.sort(key = lambda x: (x[0], -x[1]))
        # find the LIS for the height array
        height = [a[1] for a in envelopes]

        return self.lengthOfLIS(height)
        
    def lengthOfLIS(self, nums: List[int]) -> int:
        # see previous text
        pass

import "sort"

// envelopes = [[w, h], [w, h]...]
func maxEnvelopes(envelopes [][]int) int {
    n := len(envelopes)
    // sort by width in ascending order, if widths
    // are the same, sort by height in descending
    sort.Slice(envelopes, func(i, j int) bool {
        if envelopes[i][0] == envelopes[j][0] {
            return envelopes[i][1] > envelopes[j][1]
        }
        return envelopes[i][0] < envelopes[j][0]
    })
    // find the LIS for the height array
    height := make([]int, n)
    for i := 0; i < n; i++ {
        height[i] = envelopes[i][1]
    }

    return lengthOfLIS(height)
}

func lengthOfLIS(nums []int) int {
    // see previous text
}

// envelopes = [[w, h], [w, h]...]
var maxEnvelopes = function(envelopes) {
    // sort by width in ascending order, if widths
    // are the same, sort by height in descending
    let n = envelopes.length;
    envelopes.sort((a, b) => a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
    // find the LIS for the height array
    let height = new Array(n);
    for (let i = 0; i < n; i++)
        height[i] = envelopes[i][1];

    return lengthOfLIS(height);
}
  
var lengthOfLIS = function(nums) {
    // see previous text
}

To reuse the previous function, I have divided the code into two functions. You can also merge the code to save space on the height array.

Due to the addition of test cases, the lengthOfLIS function using binary search must be used to pass all test cases. In this way, the algorithm's time complexity is $O(NlogN)$, as both sorting and calculating the Longest Increasing Subsequence (LIS) require $O(NlogN)$ time, resulting in a combined complexity of $O(NlogN)$. The space complexity is $O(N)$, because the function that calculates the LIS requires a top array.