题目
/problems/longest-increasing-subsequence/
题解
难得有官方题解的一道题。
参考：/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 havenums = [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 sincemost 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 arraydp. As just stated, this array needs to representthe answer to the problem for a given state, so let’s say thatdp[i]represents the length of thelongest increasing subsequencethatends with the i-th element. The “state” is one-dimensional since it can be represented with only one variable - the indexi.
Second, we need a way to transition between states, such asdp[5]anddp[7]. This is called arecurrence relationand can sometimes be tricky to figure out. Let’s say we knowdp[0],dp[1], anddp[2]. How can we finddp[3]given this information? Well, sincedp[2]represents the length of the longest increasing subsequence that ends withnums[2], ifnums[3] > nums[2], then we can simply take the subsequence ending ati = 2and appendnums[3]to it, increasing the length by 1. The same can be said fornums[0]andnums[1]ifnums[3]is larger. Of course, we should try to maximizedp[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 ofdpto1, 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;}}
如果觉得《leetcode 300. Longest Increasing Subsequence | 300. 最长递增子序列（动态规划）》对你有帮助，请点赞、收藏，并留下你的观点哦！
