[Dynamic Programming] 1143. Longest common subsequence, 1035. Disjoint lines, 53. Maximum sum of subarrays

Tips: Live hard and have a happy day

Article directory

  • 1143. Longest common subsequence
    • Problem-solving ideas
    • Problems encountered
    • Code
    • Summary of the question
  • 1035. Disjoint lines
    • Problem-solving ideas
    • Problems encountered
    • Code
    • Summary of the question
  • 53. Maximum subarray sum
    • Problem-solving ideas
    • Problems encountered
    • Code
    • Summary of the question
  • Today’s experience

1143. Longest common subsequence

Question link: 1143. Longest common subsequence

Problem-solving ideas

  1. This question and dynamic programming: 718. The difference between the longest repeated subarray (opens new window) is that it is not required to be continuous, but there must be a relative order, that is: “ace” is a subsequence of “abcde”, but “aec” Not a subsequence of “abcde”.
  2. The Five Steps of Dynamic Rules
  • Determine the meaning of the dp array and the subscripts:dp[i][j]: The longest common length between the string text1 with a length of [0, i – 1] and the string text2 with a length of [0, j – 1] The subsequence is dp[i][j]
  • Determine the recursion formula: There are two main situations: text1[i – 1] is the same as text2[j – 1], text1[i – 1] is different from text2[j – 1]
    If text1[i – 1] is the same as text2[j – 1], then a common element is found, so dp[i][j] = dp[i - 1][j - 1] + 1;
    If text1[i – 1] and text2[j – 1] are not the same, then look at the longest common subsection of text1[0, i – 2] and text2[0, j – 1] The sequence and the longest common subsequence of text1[0, i – 1] and text2[0, j – 2], whichever is the largest.
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  • How to initialize the dp array: dp[i][0] = 0; dp[0][j] = 0
  • Determine the traversal order: From the recursion formula, it can be seen that there are three directions in which dp[i][j]
    In order to ensure that these three directions are calculated values during the recursion process, the matrix must be traversed from front to back and from top to bottom.
  • Take an example to deduce the dp array: follow the recursive formula and do the derivation. If you find that the result is wrong, print out the dp array
    The final red box dp[text1.size()][text2.size()] is the final result

Problems encountered

  1. When creating a 2D array, two string lengths + 1 are required
  2. When the traversal starts, the traversal starts from string 1, because dp[i][j]: the string text1 with the length [0, i – 1] and the string text2 with the length [0, j – 1] The longest common subsequence is dp[i][j]
  3. Termination condition for traversal, i and j can be equal to the length of the string

Code implementation

Dynamic programming

var longestCommonSubsequence = function(text1, text2) {<!-- -->
    let dp = new Array(text1.length + 1).fill(0).map(v => new Array(text2.length + 1).fill(0))
    for (let i = 1; i <= text1.length; i + + ){<!-- -->
        for (let j = 1; j <= text2.length; j + + ){<!-- -->
            if (text1[i - 1] === text2[j - 1]) {<!-- -->
                dp[i][j] = dp[i-1][j-1] + 1
            } else {<!-- -->
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
            }
        }
    }
    console.log(dp)
    return dp[text1.length][text2.length]
};

Question summary

This question and dynamic programming: 718. The difference between the longest repeated subarray (opens new window) is that it is not required to be continuous, but there must be a relative order, that is: “ace” is a subsequence of “abcde”, but “aec” Not a subsequence of “abcde”.
Therefore, there are two situations in the recursive formula, when the values of the two strings are equal or when you don’t want to wait.

1035. Disjoint lines

Question link: 1035. Disjoint lines

Problem-solving ideas

  1. Straight lines cannot intersect, which means that in string A, a subsequence that is the same as string B is found, and this subsequence cannot change the relative order. As long as the relative order does not change, straight lines linking the same numbers will not intersect. As shown below
    In fact, it means that the longest common subsequence of A and B is [1,4], with a length of 2. This common subsequence means that the relative order remains unchanged (that is, the number 4 follows the number 1 in string A, then the number 4 should also follow the number 1 in string B)
  2. This question is said to be about finding the maximum number of connections drawn, but it is actually about finding the length of the longest common subsequence of two strings! Exactly the same as the previous question

Problems encountered

none

Code implementation

dynamic programming

var maxUncrossedLines = function(nums1, nums2) {<!-- -->
    let m = nums1.length
    let n = nums2.length
    let dp = new Array(m + 1).fill(0).map(v => new Array(n + 1).fill(0))
    for (let i = 1; i <= m; i + + ){<!-- -->
        for (let j = 1; j <= n; j + + ){<!-- -->
            if (nums1[i - 1] === nums2[j - 1]) {<!-- -->
                dp[i][j] = dp[i-1][j-1] + 1
            } else {<!-- -->
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
            }
        }
    }
    console.log(dp)
    return dp[m][n]
};

Question summary

After analyzing the question thoroughly, it is actually to find the length of the longest common subsequence of two strings.

53. Maximum sum of subarrays

Question link: 53. Maximum sum of subarrays

Problem-solving ideas

  1. The Five Steps of Dynamic Rules
  • Determine the meaning of the dp array and the subscripts:dp[i]: The maximum continuous subsequence sum including the subscript i (ending with nums[i]) is dp[i].
  • Determine the recursion formula: dp[i] can be derived in only two directions:
    1. dp[i – 1] + nums[i], that is: nums[i] is added to the current continuous subsequence and
    2. nums[i], that is: calculate the sum of the current continuous subsequence from scratch
    It must be the largest, sodp[i] = max(dp[i – 1] + nums[i], nums[i]);
  • How to initialize the dp array: It can be seen from the recursive formula that dp[i] depends on the state of dp[i – 1], and dp[0] is the basis of the recursive formula. dp[0] = nums[0]
  • Determine the traversal order: dp[i] in the recursive formula depends on the state of dp[i – 1] and needs to be traversed from front to back.
  • Take an example to deduce the dp array: follow the recursion formula and do the derivation. If you find that the result is wrong, print out the dp array
    Note that the final result is not dp[nums.size() – 1]! Let’s review the definition of dp[i]: the sum of the maximum continuous subsequences including the subscript i is dp[i]. For the maximum continuous subsequence, we should find the maximum continuous subsequence with each i as the end point.

Problems encountered

1. What is finally returned is not dp[nums.size() – 1], but the largest value in the dp array

Code implementation

dynamic programming

var maxSubArray = function (nums) {<!-- -->
    let dp = new Array(nums.length).fill(0)
    dp[0] = nums[0]
    for (let i = 1; i < nums.length; i + + ){<!-- -->
        dp[i] = Math.max(nums[i],dp[i-1] + nums[i])
    }
    console.log(dp)
    return Math.max(...dp)
};

Summary of questions

This problem also has a greedy algorithm, which can be solved based on greed.
The final result of this question will be different from what you originally thought, but you need to write the entire process of the question, keeping in mind the meaning of dp[i]

Today’s experience

The recent questions on dynamic rules have a relatively deep connection with each other and can draw inferences from one instance to another.