[Golang Theme Learning month] Over the weekend, I have done several dynamic programming questions and released a super exquisite teaching version, which has a very good response. Next, I will use two languages to brush the coding questions, respectively GO and JAVA.


If you are not familiar with dynamic programming, please refer to this chapter \color{red}{if you are not familiar with dynamic programming, please refer to this chapter ~}

Liver for many days – dynamic planning ten even – super delicate analysis | brush title punch card


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?

Reference code

The language version

func lengthOfLIS(nums []int) int {
	if len(nums) < 1 {
		return 0
	}
	dp := make([]int.len(nums))
	result := 1
	for i := 0; i < len(nums); i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				dp[i] = max(dp[j]+1, dp[i])
			}
		}
		result = max(result, dp[i])
	}
	return result
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}




Copy the 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 very much talent can see here, if this article is written well, feel that there is something to ask for praise 👍 for attention ❤️ for share 👥 for handsome Oba I really very useful!!

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

At the end of this article, I recently compiled an interview material “Java Interview Process Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, databases, data structures and so on. How to obtain: GitHub github.com/Tingyu-Note… , more attention to the public number: Ting rain notes, one after another.