Leetcode 300: longest increasing subsequence

link

Ideas ： Dynamic programming （dp table）

The kernel of dynamic programming ⼼ The design idea is mathematical induction ;

If you want to prove ⼀ A mathematical conclusion , Then we Let's assume that the conclusion is k < n Shi Cheng ⽴, Then based on this assumption , Try to deduce and prove k = n This conclusion also becomes ⽴. Such as The result can be proved , So it shows that this conclusion is right for k Equal to any number ⽴.

Design dynamic programming algorithm , It's not necessary ⼀ individual dp Array ？ We can assume that dp[0…i-1] Have been calculated 了 , Then ask ⾃⼰： How to work out... From these results dp[i]？

dp Definition of array ：dp[i] Said to nums[i] The longest increment at the end of this number ⼦ The length of the sequence ;

base case：dp[i] The initial value is 1, Because in order to nums[i] The end of the most ⻓ Increasing ⼦ Sequence start The code should include it ⾃⼰.

According to this definition , Our end result （⼦ The most ⼤⻓ degree ） Should be dp Most in array ⼤ value ：

Be careful ： Not at all i The bigger it is , The longer the subsequence is ！

Suppose you already know dp[0…4] All the results of , How to deduce from these known results dp[5] ？
Such as ：

nums[5] = 3, Since it is looking for incremental ⼦ Sequence , Just find the ending in front of you 3 Small subsequences , And then put 3 To the end of these subsequences , Can form ⼀ A new increasing subsequence ,⽽ And the length of this new subsequence plus ⼀.

nums[5] front ⾯ Which elements are smaller than nums[5]？ use for Cycle comparison ⼀ Waves can find these elements .
The most... That ends with these elements ⻓ Increasing ⼦ Sequential ⻓ What is the degree ？ review ⼀ Next we are right dp Definition of array , It records exactly the most ⻓ Increasing ⼦ Sequential ⻓ degree .

In the example nums[0] and nums[4] All are less than nums[5] Of , Then contrast dp[0] and dp[4] Value , We Give Way nums[5] And longer increments ⼦ Sequence binding , obtain dp[5] = 2+1=3 ;

summary ：
1. clear dp Definition of array . this ⼀ Step is important for any dynamic programming problem , If not, or not clear enough , It will hinder the next step .

2. according to dp Definition of array , shipment ⽤ The idea of mathematical induction , hypothesis dp[0…i-1] All known , Find a way to find out dp[i],⼀ Dan this ⼀ Step through , The whole problem was basically solved .

Java Realization ：

class Solution {
    
    public int lengthOfLIS(int[] nums) {
    
         //  An element corresponds to a subsequence length , So there's no need to add  1
        int dp[]=new int[nums.length];
        Arrays.fill(dp,1); //  Ask for the biggest , Initialize to small 
        for(int i=0;i<nums.length;i++){
     // Traverse each element in turn as the end 
            for(int j=0;j<i;j++){
     //  Traverse all elements before the end element 
            //  Traverse all of   Smaller than the end element  j ,  And choose all j The longest neutron sequence , add 1 It's the result ！
                if(nums[i]>nums[j]){
     
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        
        int res=-1;
        for(int i=0;i<nums.length;i++){
    
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}