最长递增子序列：
dp 状态设计、初始化陷阱与全局最大值

子序列不要求连续，状态为何必须“以 i 结尾”？

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序即可。

初学者尝试动态规划时，最容易写出一种直觉定义：“dp[i] 表示前 i 个数里的最长递增子序列长度”。但这个定义在推导新项时会立刻陷入困境：当我们考虑 nums[i] 能否接在前面时，由于我们不知道前面子序列的末尾数值到底是多少，就根本无法判断新元素能否满足严格递增！

双重循环步进，实时推演状态转移。

观察外层循环如何固定目标结尾 nums[i]，内层循环如何向前扫描 nums[j]，并在满足 nums[j] < nums[i] 且带来更长长度时完成 dp[i] 的更新。

三个致命细节：C 初始化、严格递增与全局最大值

1. 01

   C 语言初始化陷阱：int dp[MAXN] = {1};

   在 C 语言中，语句 int dp[MAXN] = {1}; 只负责把 dp[0] 赋为 1，其后的全部元素 dp[1..n-1] 会被编译器默认补零！而在 LIS 中，每个元素自身单独成一个子序列，长度应当全部是 1。若误写此语法，未更新的项将是 0，导致算法彻底出错。必须使用 for 循环显式将全数组初始化为 1。

2. 02

   答案绝非 dp[n - 1]，必须全局求 max

   许多习惯了“背包求 dp[amount]”或“打家劫舍求 dp[n-1]”的开发者会顺手 return dp[n - 1];。但在 LIS 中，最长递增子序列的最后一个数完全可能落在数组中部（例如 [1, 5, 2]，最长序列是 [1, 5] 长度为 2，而以末尾 2 结尾的 dp[2] 仅为 2；若数组是 [1, 10, 2]，dp[1]=2，dp[2]=2；若为 [10, 20, 1]，末尾 dp[2]=1，而全局最大值是 dp[1]=2）。因此最终返回值必须是所有 dp[i] 的最大值。

3. 03

   严格递增意味着 nums[j] == nums[i] 不能接上

   题目明确要求“严格递增”（Strictly Increasing）。当 nums[j] == nums[i] 时，不能转移（即使接上长度也不会增加，且不合法）。因此转移守卫条件严格为 if (nums[j] < nums[i])。

真实 C 语言实现节选

选自 CSP 练习记录中已通过评测的源码。逻辑清晰，循环边界精准。

#include <stdio.h>

#define MAXN 2505

int lengthOfLIS(int *nums, int numsSize) {
    int dp[MAXN];

    // 避坑 1：显式初始化全部 dp[i] 为 1（每个元素自成长度为 1 的序列）
    for (int i = 0; i < numsSize; i++) {
        dp[i] = 1;
    }

    // 状态转移：外层扫描每个结尾，内层考察所有前驱候选
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
    }

    // 避坑 2：答案不是 dp[numsSize - 1]，而是全局所有 dp[i] 的最大值
    int max = 0;
    for (int i = 0; i < numsSize; i++) {
        if (dp[i] > max) {
            max = dp[i];
        }
    }
    return max;
}

复杂度与贪心二分（耐心理论）进阶