动态规划-用集合的角度推导状态转移方程 — 最长上升子序列（LIS）

用集合的角度推导状态转移方程 — 最长上升子序列（LIS）

在动态规划（Dynamic Programming, DP）中，状态转移方程是解决问题的关键。对于**最长上升子序列（Longest Increasing Subsequence, LIS）问题，除了传统的逐步推导 dp 数组的方法外，我们还可以从集合（Set）**的角度来理解和推导状态转移方程。这种方法不仅有助于深入理解问题的本质，还能为进一步优化提供理论支持。

问题回顾

目标：给定一个由整数构成的序列 nums，找到其中最长的严格递增的子序列，并返回其长度。

示例：

nums = [10, 9, 2, 5, 3, 7, 101, 18]

最长上升子序列长度：4（例如 [2, 3, 7, 101] 或 [2, 3, 7, 18]）

集合的角度理解 dp 数组

首先，我们需要重新定义动态规划数组 dp，并用集合的概念来解释其含义。

• dp[i] 的定义：

  dp[i] 表示在序列 nums 中，以第 i 个元素 nums[i] 结尾的所有上升子序列的集合。换句话说，dp[i] 包含了所有以 nums[i] 作为最后一个元素的上升子序列。

• 集合的意义：

  使用集合的角度，我们不仅关注 dp[i] 的长度，还关注具体的子序列内容。这有助于理解 dp[i] 如何通过前面的状态转移而来。

状态转移方程的集合推导

为了推导 dp[i]，我们需要考虑以下几点：

1. 前驱元素的选择：

   对于当前元素 nums[i]，它可以接在所有满足 nums[j] < nums[i] 且 j < i 的位置 j 的上升子序列之后。因此，nums[i] 可以扩展这些子序列，形成新的上升子序列。

2. 集合的合并：

   对于每一个满足条件的 j，我们将 nums[i] 添加到 dp[j] 中的每一个子序列的末尾，形成新的子序列，并将这些新的子序列加入到 dp[i] 中。

3. 长度的更新：

   因为我们希望找到最长的上升子序列，所以 dp[i] 的长度将是所有可能的 dp[j] 中的最大长度加 1。

基于以上几点，我们可以得出状态转移方程：

d p [ i ] = max ⁡ { d p [ j ]   ∣   0 ≤ j < i  且  n u m s [ j ] < n u m s [ i ] } + 1 dp[i] = \max \{ dp[j] \,|\, 0 \leq j < i \text{ 且 } nums[j] < nums[i] \} + 1 dp[i]=max{dp[j]∣0≤j<i 且 nums[j]<nums[i]}+1

其中：

• 集合的角度：

  • 所有可能的 dp[j]：即所有以 nums[j] 结尾且 nums[j] < nums[i] 的上升子序列集合。
  • 取最大值：在这些集合中选择最长的子序列长度，并加 1，表示将 nums[i] 添加到该子序列末尾。

详细推导过程

让我们通过具体示例来详细说明如何从集合的角度推导状态转移方程。

示例序列：

nums = [10, 9, 2, 5, 3, 7, 101, 18]

初始化：

• 每个 dp[i] 至少包含一个子序列，即只包含 nums[i] 本身。因此，初始时：

  dp = [{10}, {9}, {2}, {5}, {3}, {7}, {101}, {18}]
  

推导过程：

1. 步骤 i=0 (nums[0] = 10)：

   • 没有前驱元素。
   • dp[0] 保持为 {10}。

2. 步骤 i=1 (nums[1] = 9)：

   • 前驱 j=0：
     • nums[0] = 10 不满足 10 < 9。
   • dp[1] 只能包含 {9}。

3. 步骤 i=2 (nums[2] = 2)：

   • 前驱 j=0,1：
     • nums[0] = 10 不满足 10 < 2。
     • nums[1] = 9 不满足 9 < 2。
   • dp[2] 只能包含 {2}。

4. 步骤 i=3 (nums[3] = 5)：

   • 前驱 j=0,1,2：
     • nums[0] = 10 不满足 10 < 5。
     • nums[1] = 9 不满足 9 < 5。
     • nums[2] = 2 满足 2 < 5。
       • 将 5 添加到 dp[2] 的每一个子序列中：
         • {2} → {2, 5}
   • dp[3] 包含 {5} 和 {2, 5}。
   • 长度更新：dp[3] 的最长长度为 2。

5. 步骤 i=4 (nums[4] = 3)：

   • 前驱 j=0,1,2,3：
     • nums[0] = 10 不满足 10 < 3。
     • nums[1] = 9 不满足 9 < 3。
     • nums[2] = 2 满足 2 < 3。
       • 将 3 添加到 dp[2] 的每一个子序列中：
         • {2} → {2, 3}
     • nums[3] = 5 不满足 5 < 3。
   • dp[4] 包含 {3} 和 {2, 3}。
   • 长度更新：dp[4] 的最长长度为 2。

6. 步骤 i=5 (nums[5] = 7)：

   • 前驱 j=0,1,2,3,4：
     • nums[0] = 10 不满足 10 < 7。
     • nums[1] = 9 不满足 9 < 7。
     • nums[2] = 2 满足 2 < 7。
       • 将 7 添加到 dp[2] 的每一个子序列中：
         • {2} → {2, 7}
     • nums[3] = 5 满足 5 < 7。
       • 将 7 添加到 dp[3] 的每一个子序列中：
         • {5} → {5, 7}
         • {2, 5} → {2, 5, 7}
     • nums[4] = 3 满足 3 < 7。
       • 将 7 添加到 dp[4] 的每一个子序列中：
         • {3} → {3, 7}
         • {2, 3} → {2, 3, 7}
   • dp[5] 包含：
     • {7}
     • {2, 7}
     • {5, 7}
     • {2, 5, 7}
     • {3, 7}
     • {2, 3, 7}
   • 长度更新：dp[5] 的最长长度为 3。

7. 步骤 i=6 (nums[6] = 101)：

   • 前驱 j=0,1,2,3,4,5：
     • nums[0] = 10 满足 10 < 101。
       • 将 101 添加到 dp[0] 的每一个子序列中：
         • {10} → {10, 101}
     • nums[1] = 9 满足 9 < 101。
       • 将 101 添加到 dp[1] 的每一个子序列中：
         • {9} → {9, 101}
     • nums[2] = 2 满足 2 < 101。
       • 将 101 添加到 dp[2] 的每一个子序列中：
         • {2} → {2, 101}
     • nums[3] = 5 满足 5 < 101。
       • 将 101 添加到 dp[3] 的每一个子序列中：
         • {5} → {5, 101}
         • {2, 5} → {2, 5, 101}
     • nums[4] = 3 满足 3 < 101。
       • 将 101 添加到 dp[4] 的每一个子序列中：
         • {3} → {3, 101}
         • {2, 3} → {2, 3, 101}
     • nums[5] = 7 满足 7 < 101。
       • 将 101 添加到 dp[5] 的每一个子序列中：
         • {7} → {7, 101}
         • {2, 7} → {2, 7, 101}
         • {5, 7} → {5, 7, 101}
         • {2, 5, 7} → {2, 5, 7, 101}
         • {3, 7} → {3, 7, 101}
         • {2, 3, 7} → {2, 3, 7, 101}
   • dp[6] 包含：
     • {101}
     • {10, 101}
     • {9, 101}
     • {2, 101}
     • {5, 101}
     • {2, 5, 101}
     • {3, 101}
     • {2, 3, 101}
     • {7, 101}
     • {2, 7, 101}
     • {5, 7, 101}
     • {2, 5, 7, 101}
     • {3, 7, 101}
     • {2, 3, 7, 101}
   • 长度更新：dp[6] 的最长长度为 4。

8. 步骤 i=7 (nums[7] = 18)：

   • 前驱 j=0,1,2,3,4,5,6：
     • nums[0] = 10 满足 10 < 18。
       • 将 18 添加到 dp[0] 的每一个子序列中：
         • {10} → {10, 18}
     • nums[1] = 9 满足 9 < 18。
       • 将 18 添加到 dp[1] 的每一个子序列中：
         • {9} → {9, 18}
     • nums[2] = 2 满足 2 < 18。
       • 将 18 添加到 dp[2] 的每一个子序列中：
         • {2} → {2, 18}
     • nums[3] = 5 满足 5 < 18。
       • 将 18 添加到 dp[3] 的每一个子序列中：
         • {5} → {5, 18}
         • {2, 5} → {2, 5, 18}
     • nums[4] = 3 满足 3 < 18。
       • 将 18 添加到 dp[4] 的每一个子序列中：
         • {3} → {3, 18}
         • {2, 3} → {2, 3, 18}
     • nums[5] = 7 满足 7 < 18。
       • 将 18 添加到 dp[5] 的每一个子序列中：
         • {7} → {7, 18}
         • {2, 7} → {2, 7, 18}
         • {5, 7} → {5, 7, 18}
         • {2, 5, 7} → {2, 5, 7, 18}
         • {3, 7} → {3, 7, 18}
         • {2, 3, 7} → {2, 3, 7, 18}
     • nums[6] = 101 不满足 101 < 18。
   • dp[7] 包含：
     • {18}
     • {10, 18}
     • {9, 18}
     • {2, 18}
     • {5, 18}
     • {2, 5, 18}
     • {3, 18}
     • {2, 3, 18}
     • {7, 18}
     • {2, 7, 18}
     • {5, 7, 18}
     • {2, 5, 7, 18}
     • {3, 7, 18}
     • {2, 3, 7, 18}
   • 长度更新：dp[7] 的最长长度为 4。

最终结果

• dp 数组：

  dp = [
    {10},
    {9},
    {2},
    {5}, {2, 5},
    {3}, {2, 3},
    {7}, {2, 7}, {5, 7}, {2, 5, 7},
    {3, 7}, {2, 3, 7},
    {101}, {10, 101}, {9, 101}, {2, 101},
    {5, 101}, {2, 5, 101},
    {3, 101}, {2, 3, 101},
    {7, 101}, {2, 7, 101}, {5, 7, 101},
    {2, 5, 7, 101}, {3, 7, 101}, {2, 3, 7, 101},
    {18}, {10, 18}, {9, 18}, {2, 18},
    {5, 18}, {2, 5, 18},
    {3, 18}, {2, 3, 18},
    {7, 18}, {2, 7, 18}, {5, 7, 18},
    {2, 5, 7, 18}, {3, 7, 18}, {2, 3, 7, 18}
  ]
  

• 最长上升子序列的长度：4

• 可能的最长上升子序列：

  • [2, 3, 7, 101]
  • [2, 3, 7, 18]
  • [2, 5, 7, 101]
  • [2, 5, 7, 18]

状态转移方程的集合推导总结

通过上述过程，我们可以总结出从集合的角度推导状态转移方程的关键步骤：

1. 定义 dp[i] 为集合：

   • dp[i] 包含所有以 nums[i] 结尾的上升子序列。

2. 确定前驱元素：

   • 对于每一个 j < i，如果 nums[j] < nums[i]，则 nums[i] 可以接在 dp[j] 中的任何一个子序列之后。

3. 更新 dp[i]：

   • 将 nums[i] 添加到每一个满足条件的 dp[j] 的子序列中，生成新的子序列并加入到 dp[i]。

4. 提取长度信息：

   • 为了求解最长上升子序列的长度，我们只需要关注每个 dp[i] 中子序列的最大长度。
   • 因此，状态转移方程可以简化为：
     [
     dp[i] = \max { dp[j] ,|, 0 \leq j < i \text{ 且 } nums[j] < nums[i] } + 1
     ]

   其中，dp[j] 表示以 nums[j] 结尾的最长上升子序列的长度。

5. 确定最终答案：

   • 最长上升子序列的长度是所有 dp[i] 中的最大值。
   • 若需要具体的子序列内容，可以通过回溯 dp 数组来构建。

优势与应用

• 理解直观：

  从集合的角度出发，能够更直观地理解 dp[i] 的含义及其与前驱状态的关系，有助于深入理解动态规划的核心思想。

• 扩展性：

  这种方法为进一步的优化（如利用二分查找等）提供了理论基础，尤其是在需要记录具体子序列内容或进行复杂状态管理时。

实现步骤

1. 定义 dp 数组：

   • dp[i] 是一个集合，包含所有以 nums[i] 结尾的上升子序列。

2. 初始化 dp 数组：

   • 每个 dp[i] 初始包含一个仅包含 nums[i] 本身的子序列。

3. 状态转移：

   • 对于每个元素 nums[i]，遍历其之前的所有元素 nums[j]（j < i）。
   • 如果 nums[j] < nums[i]，则将 nums[i] 添加到 dp[j] 中的每一个子序列，生成新的子序列，并加入到 dp[i]。

4. 提取最长子序列长度：

   • 遍历所有 dp[i]，找到其中最长的子序列长度。

5. （可选）提取具体的最长子序列：

   • 如果需要具体的子序列内容，可以进一步处理 dp 数组。

Python 代码实现

from typing import List, Set, Tuple

def length_of_LIS_sets(nums: List[int]) -> int:
    if not nums:
        return 0
    
    n = len(nums)
    dp: List[Set[Tuple[int, ...]]] = [set() for _ in range(n)]
    
    # 初始化 dp 数组，每个 dp[i] 至少包含一个只包含 nums[i] 的子序列
    for i in range(n):
        dp[i].add( (nums[i],) )
    
    # 状态转移
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                for subseq in dp[j]:
                    new_subseq = subseq + (nums[i],)
                    dp[i].add(new_subseq)
    
    # 提取最长子序列长度
    max_length = 0
    for subseqs in dp:
        for subseq in subseqs:
            if len(subseq) > max_length:
                max_length = len(subseq)
    
    return max_length

# 示例使用
if __name__ == "__main__":
    nums = [10, 9, 2, 5, 3, 7, 101, 18]
    print(f"最长上升子序列的长度: {length_of_LIS_sets(nums)}")

代码解析

1. 导入必要的模块：

   • List, Set, Tuple 来定义类型注解，提升代码可读性。

2. 函数定义：

   • length_of_LIS_sets(nums: List[int]) -> int：接受一个整数列表 nums，返回最长上升子序列的长度。

3. 初始化 dp 数组：

   • dp = [set() for _ in range(n)]：创建一个长度为 n 的列表，每个元素是一个空集合。
   • dp[i].add( (nums[i],) )：每个 dp[i] 最初包含一个仅包含 nums[i] 的元组，表示长度为 1 的子序列。

4. 状态转移：

   • 外层循环遍历每个元素 nums[i]，从左到右。
   • 内层循环遍历 nums[i] 之前的所有元素 nums[j]（j < i）。
   • 如果 nums[j] < nums[i]，则表示可以将 nums[i] 添加到 dp[j] 中的每一个子序列，形成新的子序列，并加入到 dp[i]。

5. 提取最长子序列长度：

   • 遍历所有 dp[i] 中的子序列，找到长度最大的子序列。

6. 示例运行：

   • 使用示例序列 nums = [10, 9, 2, 5, 3, 7, 101, 18]，输出最长上升子序列的长度为 4。

输出结果

最长上升子序列的长度: 4

进一步扩展：提取具体的最长子序列

如果您不仅需要最长子序列的长度，还希望提取出具体的子序列内容，可以对上述代码进行一些修改。下面是一个扩展的版本，返回所有最长的上升子序列。

from typing import List, Set, Tuple

def find_LIS_sequences_sets(nums: List[int]) -> List[List[int]]:
    if not nums:
        return []
    
    n = len(nums)
    dp: List[Set[Tuple[int, ...]]] = [set() for _ in range(n)]
    
    # 初始化 dp 数组，每个 dp[i] 至少包含一个只包含 nums[i] 的子序列
    for i in range(n):
        dp[i].add( (nums[i],) )
    
    # 状态转移
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                for subseq in dp[j]:
                    new_subseq = subseq + (nums[i],)
                    dp[i].add(new_subseq)
    
    # 找到最长子序列的长度
    max_length = 0
    for subseqs in dp:
        for subseq in subseqs:
            if len(subseq) > max_length:
                max_length = len(subseq)
    
    # 收集所有最长子序列
    lis_sequences = []
    for subseqs in dp:
        for subseq in subseqs:
            if len(subseq) == max_length:
                lis_sequences.append(list(subseq))
    
    return lis_sequences

# 示例使用
if __name__ == "__main__":
    nums = [10, 9, 2, 5, 3, 7, 101, 18]
    sequences = find_LIS_sequences_sets(nums)
    print(f"最长上升子序列的长度: {len(sequences[0]) if sequences else 0}")
    print("所有最长上升子序列:")
    for seq in sequences:
        print(seq)

扩展代码解析

1. 函数定义：

   • find_LIS_sequences_sets(nums: List[int]) -> List[List[int]]：返回所有最长上升子序列的列表。

2. 状态转移与初始化：

   • 与前一个函数相同，dp[i] 包含所有以 nums[i] 结尾的上升子序列。

3. 提取最长子序列长度：

   • 首先确定最长子序列的长度。

4. 收集所有最长子序列：

   • 遍历 dp 数组，收集所有长度等于 max_length 的子序列。

5. 示例运行：

   • 使用相同的示例序列，输出所有最长上升子序列。

扩展输出结果

最长上升子序列的长度: 4
所有最长上升子序列:
[2, 3, 7, 101]
[2, 3, 7, 18]
[2, 5, 7, 101]
[2, 5, 7, 18]

Go 代码

package main

import (
	"fmt"
)

// lengthOfLISSets 通过集合的角度计算最长上升子序列的长度
func lengthOfLISSets(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	n := len(nums)
	// dp[i] 存储所有以 nums[i] 结尾的上升子序列
	dp := make([][][]int, n)

	// 初始化 dp 数组，每个 dp[i] 至少包含一个只包含 nums[i] 的子序列
	for i := 0; i < n; i++ {
		dp[i] = append(dp[i], []int{nums[i]})
	}

	// 状态转移
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				for _, subseq := range dp[j] {
					// 复制前一个子序列并添加当前元素
					newSubseq := append([]int{}, subseq...)
					newSubseq = append(newSubseq, nums[i])
					dp[i] = append(dp[i], newSubseq)
				}
			}
		}
	}

	// 提取最长子序列长度
	maxLength := 1
	for i := 0; i < n; i++ {
		for _, subseq := range dp[i] {
			if len(subseq) > maxLength {
				maxLength = len(subseq)
			}
		}
	}

	return maxLength
}

func main() {
	nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
	length := lengthOfLISSets(nums)
	fmt.Printf("最长上升子序列的长度: %d\n", length)
}

代码解析

1. 函数定义：

   • lengthOfLISSets(nums []int) int：接受一个整数切片 nums，返回最长上升子序列的长度。

2. 初始化 dp 数组：

   • dp := make([][][]int, n)：创建一个长度为 n 的三维切片，每个 dp[i] 是一个二维切片，存储所有以 nums[i] 结尾的子序列。
   • dp[i] = append(dp[i], []int{nums[i]})：每个 dp[i] 初始包含一个仅包含 nums[i] 的子序列。

3. 状态转移：

   • 外层循环遍历每个元素 nums[i]，从左到右。
   • 内层循环遍历 nums[i] 之前的所有元素 nums[j]（j < i）。
   • 如果 nums[j] < nums[i]，则将 nums[i] 添加到 dp[j] 中的每一个子序列，形成新的子序列，并加入到 dp[i]。

4. 提取最长子序列长度：

   • 遍历所有 dp[i] 中的子序列，找到长度最大的子序列。

5. 示例运行：

   • 使用示例序列 nums = [10, 9, 2, 5, 3, 7, 101, 18]，输出最长上升子序列的长度为 4。

输出结果

最长上升子序列的长度: 4

C++ 语言实现

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

// Function to calculate the length of LIS using set-based dynamic programming
int lengthOfLISSets(const vector<int>& nums) {
    if (nums.empty()) return 0;

    int n = nums.size();
    // dp[i] stores all increasing subsequences ending with nums[i]
    vector<vector<vector<int>>> dp(n);

    // Initialize dp array, each dp[i] contains at least the subsequence [nums[i]]
    for (int i = 0; i < n; ++i) {
        dp[i].push_back(vector<int>{nums[i]});
    }

    // State transition
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                for (const auto& subseq : dp[j]) {
                    vector<int> newSubseq = subseq;
                    newSubseq.push_back(nums[i]);
                    dp[i].push_back(newSubseq);
                }
            }
        }
    }

    // Extract the maximum length
    int maxLength = 1;
    for (int i = 0; i < n; ++i) {
        for (const auto& subseq : dp[i]) {
            if (subseq.size() > maxLength) {
                maxLength = subseq.size();
            }
        }
    }

    return maxLength;
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    int length = lengthOfLISSets(nums);
    cout << "最长上升子序列的长度: " << length << endl;
    return 0;
}

代码解析

1. 函数定义：

   • int lengthOfLISSets(const vector<int>& nums)：接受一个整数向量 nums，返回最长上升子序列的长度。

2. 初始化 dp 数组：

   • vector<vector<vector<int>>> dp(n)：创建一个长度为 n 的三维向量，每个 dp[i] 是一个二维向量，存储所有以 nums[i] 结尾的子序列。
   • dp[i].push_back(vector<int>{nums[i]})：每个 dp[i] 初始包含一个仅包含 nums[i] 的子序列。

3. 状态转移：

   • 外层循环遍历每个元素 nums[i]，从左到右。
   • 内层循环遍历 nums[i] 之前的所有元素 nums[j]（j < i）。
   • 如果 nums[j] < nums[i]，则将 nums[i] 添加到 dp[j] 中的每一个子序列，形成新的子序列，并加入到 dp[i]。

4. 提取最长子序列长度：

   • 遍历所有 dp[i] 中的子序列，找到长度最大的子序列。

5. 示例运行：

   • 使用示例序列 nums = [10, 9, 2, 5, 3, 7, 101, 18]，输出最长上升子序列的长度为 4。

输出结果

最长上升子序列的长度: 4

进一步扩展：提取所有最长上升子序列

除了计算最长上升子序列的长度，有时我们还希望获取所有的最长子序列。以下是Go和C++的扩展版本，用于返回所有最长上升子序列。

Go 语言扩展代码

package main

import (
	"fmt"
)

// findLISSequencesSets 通过集合的角度找到所有最长上升子序列
func findLISSequencesSets(nums []int) [][]int {
	if len(nums) == 0 {
		return [][]int{}
	}

	n := len(nums)
	// dp[i] 存储所有以 nums[i] 结尾的上升子序列
	dp := make([][][]int, n)

	// 初始化 dp 数组，每个 dp[i] 至少包含一个只包含 nums[i] 的子序列
	for i := 0; i < n; i++ {
		dp[i] = append(dp[i], []int{nums[i]})
	}

	// 状态转移
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				for _, subseq := range dp[j] {
					// 复制前一个子序列并添加当前元素
					newSubseq := append([]int{}, subseq...)
					newSubseq = append(newSubseq, nums[i])
					dp[i] = append(dp[i], newSubseq)
				}
			}
		}
	}

	// 找到最长子序列的长度
	maxLength := 1
	for i := 0; i < n; i++ {
		for _, subseq := range dp[i] {
			if len(subseq) > maxLength {
				maxLength = len(subseq)
			}
		}
	}

	// 收集所有最长子序列
	var lisSequences [][]int
	for i := 0; i < n; i++ {
		for _, subseq := range dp[i] {
			if len(subseq) == maxLength {
				lisSequences = append(lisSequences, subseq)
			}
		}
	}

	return lisSequences
}

func main() {
	nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
	sequences := findLISSequencesSets(nums)
	fmt.Printf("最长上升子序列的长度: %d\n", len(sequences[0]))
	fmt.Println("所有最长上升子序列:")
	for _, seq := range sequences {
		fmt.Println(seq)
	}
}

C++ 语言扩展代码

#include <iostream>
#include <vector>

using namespace std;

// Function to find all LIS sequences using set-based dynamic programming
vector<vector<int>> findLISSequencesSets(const vector<int>& nums) {
    if (nums.empty()) return {};

    int n = nums.size();
    // dp[i] stores all increasing subsequences ending with nums[i]
    vector<vector<vector<int>>> dp(n);

    // Initialize dp array, each dp[i] contains at least the subsequence [nums[i]]
    for (int i = 0; i < n; ++i) {
        dp[i].push_back(vector<int>{nums[i]});
    }

    // State transition
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                for (const auto& subseq : dp[j]) {
                    vector<int> newSubseq = subseq;
                    newSubseq.push_back(nums[i]);
                    dp[i].push_back(newSubseq);
                }
            }
        }
    }

    // Find the maximum length
    int maxLength = 1;
    for (int i = 0; i < n; ++i) {
        for (const auto& subseq : dp[i]) {
            if (subseq.size() > maxLength) {
                maxLength = subseq.size();
            }
        }
    }

    // Collect all longest subsequences
    vector<vector<int>> lisSequences;
    for (int i = 0; i < n; ++i) {
        for (const auto& subseq : dp[i]) {
            if (subseq.size() == maxLength) {
                lisSequences.push_back(subseq);
            }
        }
    }

    return lisSequences;
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    vector<vector<int>> sequences = findLISSequencesSets(nums);
    if (!sequences.empty()) {
        cout << "最长上升子序列的长度: " << sequences[0].size() << endl;
        cout << "所有最长上升子序列:" << endl;
        for (const auto& seq : sequences) {
            cout << "[";
            for (size_t i = 0; i < seq.size(); ++i) {
                cout << seq[i];
                if (i != seq.size() - 1) cout << ", ";
            }
            cout << "]" << endl;
        }
    } else {
        cout << "没有上升子序列。" << endl;
    }
    return 0;
}

扩展代码解析

1. 函数定义：

   • Go: findLISSequencesSets(nums []int) [][]int
   • C++: vector<vector<int>> findLISSequencesSets(const vector<int>& nums)

   这些函数返回所有最长上升子序列的列表。

2. 初始化 dp 数组：

   • 每个 dp[i] 初始包含一个仅包含 nums[i] 的子序列。

3. 状态转移：

   • 对于每个元素 nums[i]，检查之前的所有元素 nums[j]（j < i）。
   • 如果 nums[j] < nums[i]，则将 nums[i] 添加到 dp[j] 中的每一个子序列，形成新的子序列，并加入到 dp[i]。

4. 提取最长子序列长度：

   • 首先确定最长子序列的长度 maxLength。

5. 收集所有最长子序列：

   • 遍历所有 dp[i] 中的子序列，收集长度等于 maxLength 的子序列。

6. 示例运行：

   • 使用示例序列 nums = [10, 9, 2, 5, 3, 7, 101, 18]，输出所有最长上升子序列及其长度。

扩展输出结果

最长上升子序列的长度: 4
所有最长上升子序列:
[2, 3, 7, 101]
[2, 3, 7, 18]
[2, 5, 7, 101]
[2, 5, 7, 18]

总结

通过以上Go和C++的实现，我们展示了如何从**集合（Set）的角度使用动态规划来计算最长上升子序列（LIS）**的长度及其所有可能的子序列。这种方法有助于深入理解动态规划的状态定义和转移过程。然而，由于其高时间和空间复杂度，这种方法在实际应用中并不高效，特别是对于较大的输入序列。

推荐的更高效方法

对于实际应用，推荐使用以下更高效的算法：

1. 标准动态规划方法（时间复杂度 (O(n^2))）：

   • 使用一个 dp 数组，其中 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。
   • 通过比较前面的元素来更新 dp[i]，最终取 dp 数组中的最大值。

2. 二分查找优化方法（时间复杂度 (O(n \log n))）：

   • 使用一个辅助数组 tails，其中 tails[i] 表示长度为 i+1 的上升子序列的最小尾部元素。
   • 通过二分查找来维护 tails，从而实现高效的更新和查询。