！！！！！这道题关键的核心就在于搞懂dp[i]究竟代表什么，dp[i]表示，在以i为结尾的前提下，dp数组中每一个位置上的数都是在以i为结尾的前提下的最长子序列的长度，注意！！ 只是以i为结尾的情况，那么最长递增子序列还是要通过遍历dp数组的每个 位置，期中的最大值就是，以i位置为结尾的最长递增子序列。所以这也就是为什么题目中为什么出现Math.max(dp[i] 等等）这样的比较的语句。

思路：由于之前做的一维动态规划的问题 都是背包问题，所以我把这道题也带入到背包问题中，进行思路的构建，于是我把dp中的i视作当前的位置，dp[i]为当前位置下最长的严格递增子序列的长度。于是写出了下面的代码：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;

        int [] dp = new int[100000];
        dp[0] = 0;
        if(n == 1){
            return 1;
        }
        if(n == 2){
            if(nums[0] >= nums[1]){
                return 1;
            }else{
                return 2;
            }
        }
            dp[1]  = 1;
        for(int i = 2;i <= n;i ++){
            if(nums[i - 1] <= nums[i - 2]  ){
                dp[i] = dp[i - 1];
            }else{
                dp[i] = dp[i - 1] + 1;
            }
        }

        for(int i = 1;i <= n;i ++){
            System.out.println(dp[i]);
        }


        return dp[n];

    }
}

当然我最开始写的是：

class Solution {
    int k;
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;

        int [] dp = new int[100000];
        dp[0] = 0;
        if(n == 1){
            return nums[0];
        }
        if(n == 2){
            if(nums[0] >= nums[1]){
                k = 1;
                return 1;
            }else{
                k = 2;
                return 2;
            }
        }

            dp[1]  = 1;
            dp[2] = k;

        for(int i = 3;i <= n;i ++){
            if(nums[i - 1] <= nums[i - 2]){
                dp[i] = dp[i - 1];
            }else{
                dp[i] = dp[i - 1] + 1;
            }
        }
        return dp[n];

    }
}

这样不对，因为即使k是全局变量，但是如果不满足if的条件那么k永远不会被赋值，而我为什么要给dp[2]赋值，正是因为我的数组长度超过了2 我先给2进行初始化。犯了个低级错误 ，应该严肃多重复反思。

但是这样的方法只过了一半的样例，于是我感觉是我的方法不对，于是我去问ai，

他给我说出我这个方法的核心问题，首先这不是背包的dp，不是每个位置上的最大容量，因为当前位置的长度可能跟好久之前的位置上的数有关系。其次，这道题的最大不一定在位置最后的那个数上，而是要遍历dp数组，得到最长子序列。

上述我的代码的问题是：

1.上述代码的dp[i]没有很清晰的表示什么，因为我的dp[i]只和前一个元素相关，丢失了信息。

在正确的LIS问题中，dp[i]表示以第i个元素结尾的最长递增子序列长度，你需要遍历前面所有的元素来转移。

关键是：

要解决LIS，必须允许跳过中间元素，因此需要和前面所有元素比较。

那么如何实现上述描述的代码呢？

 代码：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int [] dp = new int[100000];
       
       for(int i = 0;i < n;i ++){
       dp[i] = 1;
        for(int j = 0;j < i;j++){
            if(nums[j] < nums[i])
            dp[i] = Math.max(dp[i],dp[j] + 1);
        }
       }

        int max = 0;
       for(int i = 0;i < n;i ++){
            max = Math.max(max,dp[i]);
            System.out.println(dp[i]);
       }

       return max;

    }
}

这道题目的核心就是 dp[i]表示以i为结尾的时候 最长递增子序列 

之前算好的 dp[0], dp[1], ..., dp[i-1] 在整个过程中从未被重置，一直保留着它们最终的、正确的值。

例子：nums = [7, 1, 8, 2]

我们逐步执行你的代码，并记录下每次循环结束后 dp 数组的状态。

初始状态（假设数组被初始化为 [0, 0, 0, 0]）：

---

i = 0（元素 7）

• 执行 dp[0] = 1 → dp = [1, 0, 0, 0]

• 内层循环 j < 0 不执行，dp[0] 最终为 1。

此时 dp = [1, 0, 0, 0]

---

i = 1（元素 1）

• 执行 dp[1] = 1 → dp = [1, 1, 0, 0]
  （注意：dp[0] 仍然保持 1，没有被重置）

• 内层循环 j = 0：nums[0]=7 < nums[1]=1? 否，不更新。

• dp[1] 最终为 1。

此时 dp = [1, 1, 0, 0]
✅ dp[0] 还是 1（之前算好的，没被改动）

---

i = 2（元素 8）

• 执行 dp[2] = 1 → dp = [1, 1, 1, 0]
  （dp[0] 和 dp[1] 仍然不变）

• 内层循环：

  • j = 0: 7 < 8 是 → dp[2] = max(1, dp[0]+1=2) = 2

  • j = 1: 1 < 8 是 → dp[2] = max(2, dp[1]+1=2) = 2

• dp[2] 最终为 2。

此时 dp = [1, 1, 2, 0]
✅ dp[0] 仍是 1，dp[1] 仍是 1，都没变

---

i = 3（元素 2）

• 执行 dp[3] = 1 → dp = [1, 1, 2, 1]
  （dp[0], dp[1], dp[2] 保持不变）

• 内层循环：

  • j = 0: 7 < 2? 否

  • j = 1: 1 < 2 是 → dp[3] = max(1, dp[1]+1=2) = 2

  • j = 2: 8 < 2? 否

• dp[3] 最终为 2。

此时 dp = [1, 1, 2, 2]
✅ dp[0]=1, dp[1]=1, dp[2]=2 始终没被后面的循环重置或修改

---

结论

• 每个 dp[i] 只在自己的外层循环中被赋值（先设为 1，再可能增大）。

• 之后当 i 变大时，之前的 dp[0..i-1] 只会被读取（用于 dp[j]），永远不会被写入或重置。

• 所以“之前已经算好的 dp[0]...dp[i-1] 并不会被重置”这句话的意思就是：每个子问题的解一旦确定，就固定不变，后面的计算只使用它，不修改它。这正是动态规划能够高效求解的基础。

第二个疑问的解答：

我们被问到：在 LIS 的 DP 解法中，dp[i] = Math.max(dp[i], dp[j] + 1); 为什么每次循环都需要跟自己比求最大值？用户可能不理解为什么不能直接赋值 dp[j] + 1。

需要解释清楚：因为内层循环遍历多个 j，每个 j 都可能产生一个候选值，我们需要保留最大的那个。所以需要用 max 函数，而不是直接赋值。同时，dp[i] 初始化为 1，然后逐步更新为更大的值。

回答要简洁清晰。

因为对于同一个 i，可能有多个 j 满足 nums[j] < nums[i]，每个 j 都会给出一个候选的 dp[j] + 1，我们需要的是其中的最大值，而不是最后一个值。

举例说明
假设 nums = [10, 9, 2, 5, 3, 7, 101, 18]，当 i=6（元素 101）时：

j=0 (10) → 候选值 dp[0]+1 = 1+1=2

j=2 (2) → 候选值 dp[2]+1 = 1+1=2

j=3 (5) → 候选值 dp[3]+1 = 2+1=3

j=4 (3) → 候选值 dp[4]+1 = 2+1=3

j=5 (7) → 候选值 dp[5]+1 = 3+1=4

j=1 (9) 不满足条件，跳过

如果不用 Math.max，而是直接 dp[i] = dp[j] + 1，那么 dp[i] 会依次被赋值为 2, 2, 3, 3, 4，最后得到 4，但其实之前的最大值也是 4，运气好可能没问题。但考虑另一个顺序：比如 j 遍历的顺序是 [1, 5, 2, 0]，那么直接赋值会导致最终结果可能为 2 或 3，取决于最后一个满足条件的 j，从而丢失真正的最大值。

更关键的是： 即使最后一个 j 恰好给了最大值，这种写法也隐含了对顺序的依赖，不是逻辑正确的做法。必须用 max 来显式地保留所有候选中的最大值。

总结
Math.max(dp[i], dp[j]+1) 的作用是：在当前的 dp[i]（已经考虑过前面某些 j 的结果）和新候选值之间取较大者。这样遍历完所有 j 后，dp[i] 自然就是以 nums[i] 结尾的最长递增子序列的长度。如果直接赋值，会丢失之前找到的更大值，导致结果错误。

第二个疑问的解答：

我们被问到：在 LIS 的 DP 解法中，dp[i] = Math.max(dp[i], dp[j] + 1); 为什么每次循环都需要跟自己比求最大值？用户可能不理解为什么不能直接赋值 dp[j] + 1。

需要解释清楚：因为内层循环遍历多个 j，每个 j 都可能产生一个候选值，我们需要保留最大的那个。所以需要用 max 函数，而不是直接赋值。同时，dp[i] 初始化为 1，然后逐步更新为更大的值。

回答要简洁清晰。

因为对于同一个 i，可能有多个 j 满足 nums[j] < nums[i]，每个 j 都会给出一个候选的 dp[j] + 1，我们需要的是其中的最大值，而不是最后一个值。

举例说明
假设 nums = [10, 9, 2, 5, 3, 7, 101, 18]，当 i=6（元素 101）时：

j=0 (10) → 候选值 dp[0]+1 = 1+1=2

j=2 (2) → 候选值 dp[2]+1 = 1+1=2

j=3 (5) → 候选值 dp[3]+1 = 2+1=3

j=4 (3) → 候选值 dp[4]+1 = 2+1=3

j=5 (7) → 候选值 dp[5]+1 = 3+1=4

j=1 (9) 不满足条件，跳过

如果不用 Math.max，而是直接 dp[i] = dp[j] + 1，那么 dp[i] 会依次被赋值为 2, 2, 3, 3, 4，最后得到 4，但其实之前的最大值也是 4，运气好可能没问题。但考虑另一个顺序：比如 j 遍历的顺序是 [1, 5, 2, 0]，那么直接赋值会导致最终结果可能为 2 或 3，取决于最后一个满足条件的 j，从而丢失真正的最大值。

更关键的是： 即使最后一个 j 恰好给了最大值，这种写法也隐含了对顺序的依赖，不是逻辑正确的做法。必须用 max 来显式地保留所有候选中的最大值。

总结
Math.max(dp[i], dp[j]+1) 的作用是：在当前的 dp[i]（已经考虑过前面某些 j 的结果）和新候选值之间取较大者。这样遍历完所有 j 后，dp[i] 自然就是以 nums[i] 结尾的最长递增子序列的长度。如果直接赋值，会丢失之前找到的更大值，导致结果错误。