小学生都能看懂的题解 | #最长上升子序列(一)#

问题描述

我们有一个数字的列表，比如 [6, 3, 1, 5, 2, 3, 7]。我们想找出这个列表中最长的“上升子序列”。

什么是上升子序列？

• 上升子序列是从原始列表中选出一些数字，这些数字要按照原来的顺序排列，且每个数字都要比前一个数字大。例如，[1, 2, 3, 7] 是一个上升子序列，因为它的每个数字都比前一个数字大。

解决方案

1. 动态规划：我们将用一个聪明的方法来解决这个问题，叫做“动态规划”。这个方法的思想是：我们逐步构建出一个结果，每一步都用到之前的结果。

2. 创建一个数组：我们会创建一个叫 dp 的数组。这个数组的每个位置 dp[i] 用来记录以 arr[i] 这个数字结尾的最长上升子序列的长度。

3. 初始化：开始时，每个数字都可以单独作为一个上升子序列，所以 dp 数组的每个位置初始值都为 1。

4. 逐步比较：

   • 对于每一个数字，我们去看它之前的所有数字。
   • 如果当前的数字比之前的数字大，说明可以把当前数字加到之前的上升子序列中。我们就更新 dp[i] 的值为之前的最长上升子序列长度加上1（也就是加上当前这个数字）。

5. 找出最长的序列：最后，我们只需要找到 dp 数组中最大的值，这就是我们要找的最长上升子序列的长度。

代码解释

下面是我们写的代码，逐行解释它的作用：

public class LongestIncreasingSubsequence {
    
    public static int lengthOfLIS(int[] arr) {
        int n = arr.length; // 获取数组的长度
        if (n == 0) return 0; // 如果数组为空，返回0
        
        int[] dp = new int[n]; // 创建一个 dp 数组来存储结果
        int maxLength = 1; // 最少有一个数字，所以初始最长长度为1
        
        for (int i = 0; i < n; i++) {
            dp[i] = 1; // 初始化每个位置的 dp 值为1
        }
        
        for (int i = 1; i < n; i++) { // 从第二个数字开始遍历
            for (int j = 0; j < i; j++) { // 比较之前的所有数字
                if (arr[i] > arr[j]) { // 如果当前数字大于之前的数字
                    dp[i] = Math.max(dp[i], dp[j] + 1); // 更新 dp[i] 的值
                }
            }
            maxLength = Math.max(maxLength, dp[i]); // 更新最长的上升序列长度
        }
        
        return maxLength; // 返回最长上升子序列的长度
    }
    
    public static void main(String[] args) {
        int[] arr = {6, 3, 1, 5, 2, 3, 7}; // 输入的数组
        int result = lengthOfLIS(arr); // 计算结果
        System.out.println("最长严格上升子序列的长度是: " + result); // 输出结果
    }
}

每行代码的作用

• public class LongestIncreasingSubsequence: 定义一个类，里面写我们的程序。
• public static int lengthOfLIS(int[] arr): 定义一个方法，这个方法接受一个数字数组，并返回最长上升子序列的长度。
• int n = arr.length;: 获取数组的长度。
• if (n == 0) return 0;: 如果数组没有数字，直接返回 0。
• int[] dp = new int[n];: 创建一个 dp 数组，大小和输入数组一样。
• for (int i = 0; i < n; i++) { dp[i] = 1; }: 初始化 dp 数组，每个位置都设为 1。
• for (int i = 1; i < n; i++) { ... }: 从第二个数字开始，逐个与前面的数字比较。
• if (arr[i] > arr[j]) { ... }: 如果当前数字大于某个前面的数字，就更新 dp[i]。
• maxLength = Math.max(maxLength, dp[i]);: 每次更新最长上升序列的长度。
• return maxLength;: 最后返回最长的上升子序列的长度。
• public static void main(String[] args) { ... }: 主方法，程序的入口点，调用我们定义的方法并输出结果。

希望这篇文章对你有帮助👍。