Topic describes

Their thinking

  • This problem in JS problem solution generally gives two solutions, one is dynamic programming, the second is greedy algorithm
  • Dynamic programming is adopted this time, mainly to strengthen their own learning in this area
  • The greedy idea is to construct 3, multiply as many 3’s as possible to maximize the product, and derive the final product separately by taking the remainder of 3
  • The ideas of the dynamic programming is first constructed a whole length of the n + 1 1 array, where n represents the total length of the rope, the reason for + 1, because of our operation is always an array subscript, dp [I] represent what meaning, is what we have to have a good understanding, dp [I] represents the length of the rope I cut into the largest product after n pieces
  • The end condition of the dynamic programming is dp[2]=1, because 2 meters of rope can be split into 1+1, and the final product is 1
  • Dynamic planning of general equation is dp [I] = Max (dp [I], j * (I – j) and dp (I – j] j *)
  • Understanding the general equation above is key to solving this problem, dp[I] is the largest product of the string of length I that is continuously modified by cutting it into n pieces, where I is traversed from 3, j is traversed from 1, and i-j represents the length of the other piece if one piece of string is split in two, But j * (i-j) is just judging all the results of a piece of string cut in two, but sometimes the largest product is the product of three or more numbers, like the string length is eight, and then you can split it into 3 * 3 * 2 = 18, so the third equation of dynamic programming is crucial, j starts at one, So the first I minus j is 7, so the sum of I and I minus j is always 8, and when I is 2 and I minus j is 6 you get 2 * 3 * 3 which is the maximum product that we’re looking for, by j * dp[i-j] will implicitly introduce a shorter product of numbers, rather than just multiplying two by two.

To help understand this, I made the following diagram, using DP [4] as an example, to understand the dynamic programming in this problem

The problem solving code

var cuttingRope = function(n) {
    // Dynamic programming can be used in this topic
    // The end condition of the dynamic programming is dp[2] = 1, which means that the maximum product of a string of length 2 is 1
    const dp = new Array(n + 1);
    dp.fill(1);
    for (let i = 3; i < dp.length; i++) {for (let j = 1; j < i; j++) { dp[i] =Math.max(dp[i],j*(i-j),j*dp[i-j])
        }
    }
    return dp[n]
};
Copy the code

Conclusion (this topic gives us the enlightenment of thinking)

  • Revelation 1: Learn to make dynamic planning
  • Lesson 2: Learn how to traverse two elements of value x