This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021

The basic concept

• A general technique for dynamic programming: the idea of mathematical induction
• Longest increasing subsequenceLISQuestion:
  • Dynamic programming solution. Time is O(N^2^).
  • Binary search solution. Time complexity is O(Nlog⁡N)O(N\log N)O(NlogN)
• Note:The difference between subsequences and substrings
  • Subsequences are not necessarily continuous
  • The substring must be continuous

Dynamic programming solution

• The core idea of dynamic programming is mathematical induction

• To prove a mathematical conclusion:
  • Let’s assume that this is true when k
  • And then we show that this is also true if k=nk =nk =n
  • So that means that this is true if K k is equal to anything

• Dynamic programming algorithm:The need for aDPAn array of
  • [0,…, I can assume that dp – 1] dp [0,…, I – 1] dp [0,…, I – 1] has been calculated
  • Dp [I]dp[I]dp[I]
• The longest increasing subsequence LIS problem:
  • The first step is to define the DPDPDP array
  • Dp [I]dp[I]dp[I
• Definition: dp[I]dp[I]dp[I] indicates the length of the longest increasing subsequence ending in nums[I]nums[I]
• By definition, the maximum length of the subsequence of the final result is the maximum in the DP array

int res = 0;
for (int i = 0; i < dp.size(); i ++) {
	res = Math.max(res, dp[i]);
}
return res;
Copy the code

• Design dynamic programming algorithms to correctly calculate each
  $dp[i]$: Using mathematical induction to think about how to do state transitions
  • According to the definition of a dp array, known dp [0,…, 4] dp [0,…, 4] dp [0,…, 4] as a result, for dp [5] dp [5] dp value of [5], which would require nums [5] nums [5] nums [5] for the end of the longest increasing subsequence
  • Nums [5]= 3NUMs [5]= 3NUMs [5]=3, because it is an increasing subsequence, as long as you find the previous increasing subsequence whose end is smaller than 3, and then join 3 to the end, you can form a new increasing subsequence, and the length of this new sequence will increase by 1
  • There are many kinds of sub-sequences formed, but the longest one is needed. The length of the oldest sequence is taken as the value of DP [5]dp[5]

  for (int j = 0; j < i, j++) {
  	if (nums[i] > nums[j]) {
  		dp[i] = Math.max(dp[i], dp[j] + 1); }}Copy the code

  • Using mathematical induction, you can calculate the values of the remaining DP array

  for (int i = 0; i < nums.length; i++) {
  	for (int j = 0; j < i; j++) {
  		if (nums[i] > nums[j]) {
  			dp[i] = Math.max(dp[i], dp[j] + 1); }}}Copy the code

  • The dp array should all be initialized to 1, because the subsequence is at least as long as it contains itself, so the minimum length is 1 instead of 0
• Longest increasing subsequence complete code:

public int lengthOfLIS(a) {
	int[] dp = new int[nums.length];
	// all dp arrays are initialized to 1
	Arrays.fill(dp, 1);
	for (int i = 0; i < nums.length; i++) {
		for (int j = 0; j < i; j++) {
			if (nums[i] > nums[j]) {
				dp[i] = Math.max(dp[i], dp[j] + 1); }}}int res = 0;
	for (int i = 0; i < dp.length(); i++) {
		res = Math.max(res, dp[i]);
	}
	return res;
}
Copy the code

• The time complexity of DP array algorithm for longest increasing subsequence is O(N^2^).
• Dynamic planning and design process:
  • The first step is to clarify the meaning of the data stored in the DP array
    • This step is very important, and if the meaning is not clear, it can lead to confusion in the calculation of subsequent steps
  • And then, based on the definition of DP array, calculate
    $dp[i]$
    • Using the idea of mathematical induction, suppose
      $dp[0,…,i-1]$The values of are all known according to
      $dp[0,…,i-1]$The value of the work out
      $dp[i]$
      • Once this step is done, the whole problem is basically solved
      • If this is not possible, you need to rethink the definition of DP arrays
      • Or it may be that the information stored in the DP array is not complete and the next answer cannot be derived, so it is necessary to expand the DP array into a two-dimensional array or even a three-dimensional array
  • Finally determine the base case of the problem
    • Base case is used to initialize the array to ensure the correct operation of the algorithm

Binary search solution

• The algorithm time complexity of binary search for the longest increasing subsequence is O(Nlog⁡N)O(N\log N)O(NlogN)
• The longest increasing subsequence is related to a card game called patience Game. There is a sorting algorithm called patience sorting
• Scenario analysis:Given a row of cards, proceed from left to right like a sequence of cards, one by one, and finally divide the cards into piles
  • You can only put a small card on a big one
  • If the current card count is too large and there is no heap to place, a new heap is created and the card is placed in it
  • If the current card has more than one heap to choose from, the leftmost heap is chosen for placement
    • The leftmost pile was chosen to keep the cards on top of the pile in order
• According to the above rules, the longest increasing subsequence can be calculated, and the deck number is the length of the longest increasing subsequence
• Binary search algorithm for the longest increasing subsequence:
  • The process of dealing with cards is expressed programmatically
  • Because each time you deal with a card to find an appropriate deck top to place, the deck top cards are in order. So you can use binary search
  • Use binary search to search where the current card should be placed

public int LengthOfLIS(int[] nums) {
	int[] top = new Int[nums.length];
	// The stack of cards is initialized to 0
	int piles = 0;

	for (int i = 0; i < nums.length; i++) {
		// The card that needs to be processed
		int poker = nums[i];

		int left = 0, right = piles;
		while (left < right) {
			int mid = left + (right -left) / 2;
			if (top[mid] > poker) {
				right = mid;
			} else if (top[mid] < poker) {
				left = mid + 1;
			} else{ right = mid; }}// Create a new deck if no suitable deck is found
		if (left == piles) {
			piles++;
		}
		// Select the leftmost deck to place
		top[left] = piles;
	}
	// The deck number is the length of the longest increasing substring
	return piles;
}
Copy the code

• Binary search solution:
  • The first involves mathematical proof that the longest increasing subsequence can be obtained by executing these rules
  • Secondly is the application of binary search algorithm, to understand the details of binary search method
• Dynamic programming design method:
  • So let’s say we know the answer
  • Use the idea of mathematical induction to transfer state correctly
  • And finally get the answer

• Dynamic programming solution:

def lengthOfLIS(self, nums : List[int]) - >int:
	n = len(nums)
	dp = [1 for x in range(0, n)]
	for i in range(0, n):
		for j in range(0, i):
			if nums[i] > num[j]:
				dp[i] = max(dp[i], dp[j] + 1)
	res = 0
	for temp in dp:
		res = max(temp, res)
	return res
Copy the code

• Binary search solution:

def lengthOfLIS(self, nums : List[int]) - >int:
	top = []
	The deck is initialized to 0
	piles = 0
	# num is the card to be processed
	for num in nums:
		left, right = 0.while left < right:
  	mid = left + (right - left) / 2
  	# Search the left edge
  	if top[mid] > num:
  		right = mid
  	# Search the right edge
  	elif top[mid] < num:
  		left = mid + 1
  	else
  		right = mid
  if left == piles:
  	If no suitable deck is found, create a new deck
  	piles += 1
  # Put this card on top of the new deck
  top[left] = num
  The deck number is the length of the longest increasing subsequence
  return piles
Copy the code