动态规划设计：最长递增子序列

labuladong原创动态规划设计约 4049 字

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	Difficulty
300. Longest Increasing Subsequence	🟠
354. Russian Doll Envelopes	🔴

Prerequisites

Before reading this article, you should learn:

Dynamic Programming Core Framework

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:

300. Longest Increasing Subsequence | 力扣 | LeetCode |

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

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.

Example 2:

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

Example 3:

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

Constraints:

1 <= nums.length <= 2500
-10⁴ <= nums[i] <= 10⁴

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

// 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 contiguous. Let's design a dynamic programming algorithm to solve this problem.

Dynamic Programming Solution

The core design idea of dynamic programming is mathematical induction.

Most of you are familiar with mathematical induction, which you learned in high school. The concept is straightforward. For instance, if we want to prove a mathematical statement, we first assume the statement holds for k < n, and then based on this assumption, we try to derive and prove that the statement also holds for k = n. If we can prove this, it means the statement is true for any value of k.

Similarly, in designing a dynamic programming algorithm, we need a dp array, right? We can assume that dp[0...i-1] has already been calculated and then ask ourselves: how can we use these results to calculate dp[i]?

Let's take the longest increasing subsequence problem as an example. First, we need to clearly define what the dp array represents, i.e., what does the value of dp[i] signify?

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

相关信息

Why define it this way? This is a common approach to solving subsequence problems. The article Dynamic Programming Template for Subsequence Problems summarizes several common approaches. You'll find that after reading all the dynamic programming problems in this chapter, there are only a few ways to define the dp array.

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

Here are two examples:

This GIF shows the evolution of the algorithm:

According to 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 evolution of the algorithm just discussed, each dp[i] result was determined by visual inspection. How should we design the algorithm logic to correctly calculate each dp[i]?

This is the crux of dynamic programming: how to design the logic for state transitions to ensure correct operation? Here, we need to use the concept of mathematical induction:

Assume we already know all the results for dp[0..4]. How can we use these known results to derive dp[5]?

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

nums[5] = 3. Since it's an increasing subsequence, we just need to find the subsequences before it that end with a number less than 3, and then append 3 to the end of these subsequences to form a new increasing subsequence, with the length increased by one.

Which elements before nums[5] are smaller than nums[5]? This is easy to calculate; a simple for loop can identify these elements.

What is the length of the longest increasing subsequence ending with these elements? Reviewing our definition of the dp array, it records exactly the length of the longest increasing subsequence ending with each element.

In our example, both nums[0] and nums[4] are smaller than nums[5]. By comparing the values of dp[0] and dp[4], we let nums[5] combine with the longer increasing subsequence, resulting in 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..j-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:

java 🟢

class Solution {
    public int lengthOfLIS(int[] nums) {
        // Definition: dp[i] represents the length of the longest increasing subsequence ending with nums[i]
        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;
    }
}

cpp 🤖

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // Definition: dp[i] represents the length of the longest increasing subsequence ending with nums[i]
        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;
    }
};

python 🤖

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # Definition: dp[i] represents the length of the longest increasing subsequence ending with nums[i]
        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

go 🤖

func lengthOfLIS(nums []int) int {
    // Definition: dp[i] represents the length of the longest increasing subsequence ending with nums[i]
    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
}

javascript 🤖

var lengthOfLIS = function(nums) {
    // Definition: dp[i] represents the length of the longest increasing subsequence ending with nums[i]
    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;
};

With this, the problem is solved, with a time complexity of O(N^2). Let's summarize how to find the state transition relationship in dynamic programming:

Define the dp array clearly. This step is crucial for any dynamic programming problem. If it's not appropriate or clear enough, it will hinder the subsequent steps.
Based on the definition of the dp array, use mathematical induction. Assume dp[0...i-1] is known and try to derive dp[i]. Once this step is completed, the problem is essentially solved.

If you can't complete this step, it's likely that the definition of the dp array is not suitable and needs to be redefined. Alternatively, the dp array might not store enough information to deduce the next step, in which case you might need to expand it to a two-dimensional or even three-dimensional array.

The current solution is a standard dynamic programming approach, but for the longest increasing subsequence problem, this method is not the most efficient and may not pass all test cases. Next, we'll discuss a more efficient solution.

Section 2: Binary Search Solution

This solution has a time complexity of O(NlogN). However, to be honest, it's not something most people would think of (perhaps those who have played certain card games might). So, it's good to be aware of it, but under normal circumstances, being able to provide a dynamic programming solution is already quite impressive.

Based on the problem statement, it's hard to imagine that this issue could be related to binary search. Actually, the longest increasing subsequence is related to a card game called the patience game, and there's even a sorting method named patience sorting.

For simplicity, we'll skip all the mathematical proofs and understand the algorithm's approach through a simplified example.

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

Handling these playing cards follows these rules:

You can only place a card with a smaller value on top of a card with a larger value.
If the current card has no larger pile to be placed on, create a new pile and put this card in it.
If the current card can be placed on multiple piles, choose the leftmost pile.

For example, the above playing cards will eventually be divided into 5 piles (we consider card A to have the highest value and card 2 to have the lowest value).

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

Following these rules, you can determine the longest increasing subsequence. The number of piles is the length of the longest increasing subsequence. The proof is omitted.

We just need to program the process of handling the playing cards. Each time we handle a card, we need to find a suitable pile top to place it on. Since the top cards of the piles are sorted, we can use binary search: use binary search to find the position where the current card should be placed.

提示

The previous article Binary Search Algorithm Explained provides a detailed introduction to binary search and its variants. It is perfectly applicable here. If you haven't read it, I strongly recommend doing so.

java 🟢

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;
    }
}

cpp 🤖

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;
    }
};

python 🤖

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

go 🤖

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
}

javascript 🤖

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.

III. Extending to Two Dimensions

Let's look at an interesting real-life problem, LeetCode problem #354 "Russian Doll Envelopes." First, let's see the question:

354. Russian Doll Envelopes | 力扣 | LeetCode |

You are given a 2D array of integers envelopes where envelopes[i] = [w_i, h_i] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Example 1:

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]).

Example 2:

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

Constraints:

1 <= envelopes.length <= 10⁵
envelopes[i].length == 2
1 <= w_i, h_i <= 10⁵

This problem is actually a variation of the Longest Increasing Subsequence (LIS). Each valid nesting (larger envelope containing a smaller one) is equivalent to finding the longest increasing subsequence in a two-dimensional plane. The length of this subsequence represents the maximum number of envelopes that can be nested.

The standard LIS algorithm we discussed earlier can only find the longest subsequence in a one-dimensional array. However, our envelopes are represented by two-dimensional pairs (w, h). How can we apply the LIS algorithm here?

You might think of calculating the area using w × h and then applying the standard LIS algorithm to these areas. But upon closer consideration, this approach doesn't work. For example, 1 × 10 is larger than 3 × 3, but clearly, these two envelopes cannot be nested within each other.

The solution to this problem is quite clever:

First, sort the width w in ascending order. If w values are the same, sort the height h in descending order. Then, treat all h values as an array and calculate the length of the Longest Increasing Subsequence (LIS) in this array. This length is the answer.

Let's visualize this by first sorting these pairs:

Then, find the longest increasing subsequence in h. This subsequence represents the optimal nesting scheme:

Why does this method find the sequence of envelopes that can be nested within each other? Think about it for a moment:

First, sorting the width w from smallest to largest ensures that the envelopes can nest within each other in the w dimension. Therefore, we only need to focus on ensuring that the height h dimension can also nest.

Second, envelopes with the same w cannot contain each other. So, for envelopes with the same width w, sort the height h in descending order. This ensures that there are no multiple envelopes with the same w in the two-dimensional LIS (since the problem states that envelopes with the same dimensions cannot nest).

Now, let's look at the solution code:

java 🟢

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 order
        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
    }
}

cpp 🤖

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 order
        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
    }
};

python 🤖

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 descending order
        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

go 🤖

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 order
    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
}

javascript 🤖

// 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 order
    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 divided the code into two functions. You can also merge the code to save space in the height array.

Since we have added more test cases, we must use the binary search version of the lengthOfLIS function to pass all test cases. This way, the time complexity of the algorithm is O(NlogN), because both sorting and calculating LIS each take O(NlogN) time, which together still results in O(NlogN). The space complexity is O(N), as the LIS calculation function requires a top array.

引用本文的题目

安装我的 Chrome 刷题插件点开下列题目可直接查看解题思路：

LeetCode	力扣
1425. Constrained Subsequence Sum	1425. 带限制的子序列和
256. Paint House🔒	256. 粉刷房子🔒
368. Largest Divisible Subset	368. 最大整除子集
-	剑指 Offer II 091. 粉刷房子

动态规划设计：最长递增子序列

300. 最长递增子序列 https://leetcode.cn/problems/longest-increasing-subsequence

300. Longest Increasing Subsequence https://leetcode.com/problems/longest-increasing-subsequence

354. 俄罗斯套娃信封问题 https://leetcode.cn/problems/russian-doll-envelopes

354. Russian Doll Envelopes https://leetcode.com/problems/russian-doll-envelopes

Dynamic Programming Solution

Section 2: Binary Search Solution

III. Extending to Two Dimensions