You need to figure out the subproblems, and then solve all of them by solving one subproblem at a time,
First, the problem should be able to be disassembled;
Second, these small problems should be able to be solved
300. Longest increasing subsequence
And this is done by creating a list of the maximum increasing subsequences at the current location,
And then compare them one by one,
If the current coordinate is greater than the value of the element in the maximum increment subsequence,
To modify the element value of the current coordinate, increment the element value corresponding to the value in the subsequence by +1.
That means we have two arrays one that they gave us and one that we created
An array of integers and corresponding subsequences
One thing they have in common is that they have the same index.
I’m going to use this same sex and then I’m going to add another property
It’s inheritance, because what they’re asking for is an increasing sequence, which is when this number is greater than something before it,
I can inherit the corresponding length, and make it longer by plus 1
Given an integer array nums, find the length of the longest strictly increasing subsequence.
A subsequence is a sequence derived from an array that deletes (or does not delete) the elements of the array without changing the order of the rest of the elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Example 1:
Input: nums = [10,9,2,5,3,7,101,18] output: 4 explanation: the longest increasing subsequence is [2,3,7,101], so length is 4. Example 2:
Input: nums = [0,1,0,3, 3] Output: 4 Example 3:
Input: nums = [7,7,7,7,7] Output: 1
Tip:
1 <= nums.length <= 2500 -104 <= nums[i] <= 104
Advanced:
Can you design a solution with O(n2) time? Can you reduce the time complexity of the algorithm down to order n log n?
Source: LeetCode link: leetcode-cn.com/problems/lo… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
354. Russian nesting envelope problem
This is also using dynamic programming,
First of all, let’s analyze the problem. What the problem needs is that each envelope can be continuously nested,
Then, as long as the latter envelope is wider and taller than the previous one, slip it inside.
So, the first thing to do is sort the envelopes,
Sort by width, if the width is the same, sort by height.
For the sorted array,
Starting with the second envelope and looking for the previous envelope,
If the previous envelope exists wider and taller than that,
Just add one to the previous record.
You are given a two-dimensional integer array envelopes, where envelopes[I] = [wi, hi] represents the width and height of the i-th envelope.
When the width and height of another envelope are larger than this one, this envelope can be put into another envelope, like a Russian nesting doll.
Please calculate the maximum number of envelopes that can make up a group of matryoshka envelopes (i.e. one envelope can be placed inside another envelope).
Note: Rotating the envelope is not allowed.
Example 1:
Input: envelopes = [[5, 4], [6, 4], [6, 7], [2, 3]] output: 3: most of the envelope number 3, combination is: [2, 3] = > [5, 4] = > [6, 7]. Example 2:
Input: envelopes = [[1,1],[1,1]] Output: 1
Tip:
1 <= envelopes.length <= 5000 envelopes[i].length == 2 1 <= wi, hi <= 104
Source: LeetCode link: leetcode-cn.com/problems/ru… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
/** * @param {number[][]} envelopes * @return {number} */ var maxEnvelopes = function(envelopes) Var code = [] if(envelopes. Length == 1){return 1} var envelopes = envelopes.sort((a,b)=>{ if(a ! == b){return a[0] -b [0]}else{return a[1] -b [1]}}) var tem_envelopes = envelopes For (var I = 0; var I = 0; i < envelopes.length; i++){ code[i] = 0 for(var j = 0; j <= i; j++){ if(envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]){ code[i] = Math.max(code[i],code[j]) } } code[i]++ } code = code.sort((a,b) => {return b - a}) return code[0] };Copy the code