线性dp LIS

线性动态规划（Linear Dynamic Programming）在许多问题中都有广泛的应用，其中一个典型的问题是最长递增子序列（Longest Increasing Subsequence，简称 LIS）问题。LIS 问题的目标是找到一个给定序列中的最长递增子序列的长度，其中递增子序列指的是序列中的元素按照顺序递增排列。

以下是最长递增子序列问题的一般步骤：

1. 定义状态：通常使用一个数组 dp，其中 dp[i] 表示以第 i 个元素为结尾的最长递增子序列的长度。

2. 状态转移方程：对于第 i 个元素，我们需要找到前面所有比它小的元素中，以它们为结尾的最长递增子序列的最大长度。状态转移方程可以表示为：

   dp[i] = max(dp[j] + 1), 其中 0 <= j < i 且 nums[j] < nums[i]

   这意味着我们在计算 dp[i] 时，会考虑前面所有满足条件的 dp[j] 的最大值加 1。

3. 边界条件：初始时，每个元素自成一个长度为 1 的递增子序列，所以 dp[i] = 1。

4. 计算顺序：通常从小规模问题开始，逐步计算出大规模问题的最优解。

下面是一个最长递增子序列问题的 Java 代码示例：

public class LongestIncreasingSubsequence {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        int maxLength = 0;
        for (int len : dp) {
            maxLength = Math.max(maxLength, len);
        }
        
        return maxLength;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int maxLength = lis.lengthOfLIS(nums);
        System.out.println("Length of longest increasing subsequence: " + maxLength);
    }
}

在这个示例中，我们使用动态规划解决了最长递增子序列问题。通过遍历每个元素，根据状态转移方程计算以当前元素为结尾的最长递增子序列长度。最终，我们在 dp 数组中找到最大的长度，即为最长递增子序列的长度。

请注意，LIS 问题的动态规划解法可能因为问题的具体要求而有所变化，但通常都涵盖了上述的状态定义、状态转移方程和边界条件。