This article is participating in the “Java Theme Month – Java brush questions clock”, see < activity links > for more details.

【Java brush questions punch card 】 Brushing questions is much better than playing games, and the sense of achievement is getting stronger and stronger. I insist on brushing several questions every day, exercising for 30 minutes every day, waiting for 8-block abs and waiting for offers from big factories.

Then do it! This column is all about dynamic planning, I will start from the shallow to the deep, step by step, brush questions is such a need for continuous memory – Ebbinghaus memory method 2121112. There isn’t much about dynamic programming, but it’s a must for every programmer


This is a simple question 😄😄😄 \color{green}{😄 😄 😄 ~}

What problem can I choose to do dynamic programming?

Counting 1.

  • How many ways can I get to the bottom right corner
  • How many ways can I pick the sum of k numbers yes is sum

2. Find the maximum and minimum

  • The maximum numeric sum of the path from the upper left corner to the lower right corner
  • Maximum ascending subsequence length

3. Seek existence

  • Stone game, whether the first hand will win
  • Can we pick k numbers such that the sum is sum

4. Comprehensive application

  • Dynamic planning + hash
  • Dynamic programming + recursion
  • .

Leecode 300. Longest increasing subsequence

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] and therefore has a length of 4.

Example 2:

Input: nums = [0,1,0,3,2,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?

—

❤ ️ ❤ ️ ❤ ️ ❤ ️

2.1. Dynamic planning component 1: State determination

To put it simply, when solving dynamic programming, you need to open an array. What does each element of the array f[I] or f[I][j] represent, similar to what x, y, and z represent in mathematical problems

The last step

We define dp[I] as the length of the longest ascending subsequence ending in the ith digit, considering the first I elements

Max {d[I], d[j] +1, Max {d[I] +1, Max {d[I], d[j] +1}

The final step, such as nums = [0,1,0,3,2,9], is to match the preceding number with the 9 block, find the number less than I, and record the occurrence

1.2. Dynamic programming component 2: Transfer equation

dp[i] = Math.max(dp[i], dp[j] + 1);

1.3. Dynamic programming component 3: initial conditions and boundary cases

dp[0] = 1;

int maxans = 1; // The minimum time

1.4. Dynamic programming component 4: Order of calculation

Each I matches the preceding 0 to I -1


Great! 😄 😄 😄 \ color {green} {! 😄 😄 😄 ~}

Reference code


N I C E Easy 😄😄😄 \color{red}{NICE too simple 😄 😄 😄 ~}

Java version

  class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 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);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        returnmaxans; }}Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️