leetcode 300. Longest Increasing Subsequence | 300. 最长递增子序列（动态规划）

雨点打透心脏的1/2处 2022-10-12 14:59 198阅读 0赞

## 题目 ##

[https://leetcode.com/problems/longest-increasing-subsequence/][https_leetcode.com_problems_longest-increasing-subsequence]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

难得有官方题解的一道题。

参考：[https://leetcode.com/problems/longest-increasing-subsequence/solution/][https_leetcode.com_problems_longest-increasing-subsequence_solution]

#### Approach 1: Dynamic Programming ####

**Realizing a Dynamic Programming Problem**

This problem has two important attributes that let us know it should be solved by dynamic programming. First, the question is asking for the maximum or minimum of something. Second, we have to make decisions that may depend on previously made decisions, which is very typical of a problem involving subsequences.

As we go through the input, each “decision” we must make is simple: is it worth it to consider this number? If we use a number, it may contribute towards an increasing subsequence, but it may also eliminate larger elements that came before it. For example, let’s say we have `nums = [5, 6, 7, 8, 1, 2, 3]`. It isn’t worth using the 1, 2, or 3, since using any of them would eliminate 5, 6, 7, and 8, which form the longest increasing subsequence. We can use dynamic programming to determine whether an element is worth using or not.

**A Framework to Solve Dynamic Programming Problems**

Typically, dynamic programming problems can be solved with three main components. If you’re new to dynamic programming, this might be hard to understand but is extremely valuable to learn since **most dynamic programming problems can be solved this way**.

First, we need some function or array that represents the answer to the problem from a given state. For many solutions on LeetCode, you will see this function/array named “dp”. For this problem, let’s say that we have an array `dp`. As just stated, this array needs to represent **the answer to the problem for a given state**, so let’s say that `dp[i]` represents the length of the **longest increasing subsequence** that **ends with the i-th element**. The “state” is one-dimensional since it can be represented with only one variable - the index `i`.

Second, we need a way to transition between states, such as `dp[5]` and `dp[7]`. This is called a **recurrence relation** and can sometimes be tricky to figure out. Let’s say we know `dp[0]`, `dp[1]`, and `dp[2]`. How can we find `dp[3]` given this information? Well, since `dp[2]` represents the length of the longest increasing subsequence that ends with `nums[2]`, if `nums[3] > nums[2]`, then we can simply take the subsequence ending at `i = 2` and append `nums[3]` to it, increasing the length by 1. The same can be said for `nums[0]` and `nums[1]` if `nums[3]` is larger. Of course, we should try to maximize `dp[3]`, so we need to check all 3. Formally, the recurrence relation is: `dp[i] = max(dp[j] + 1) for all j where nums[j] < nums[i] and j < i`.

The third component is the simplest: we need a base case. For this problem, we can initialize every element of `dp` to `1`, since every element on its own is technically an increasing subsequence.

**Implementation**

class Solution { 
        public int lengthOfLIS(int[] nums) { 
            int[] dp = new int[nums.length]; // 强制包含当前元素时的最大值
            dp[0] = 1;
            for (int i = 1; i < nums.length; i++) { 
                dp[i] = 1;
                for (int j = 0; j <= i; j++) { 
                    if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            
            int max = 1;
            for (int n : dp) { 
                max = Math.max(n, max);
            }
            return max;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

[https_leetcode.com_problems_longest-increasing-subsequence]: https://leetcode.com/problems/longest-increasing-subsequence/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/9b44fcc9795644f48d9ad12ded231005.png
[https_leetcode.com_problems_longest-increasing-subsequence_solution]: https://leetcode.com/problems/longest-increasing-subsequence/solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/4ab037d272ed4b25b742ec4010af1805.png