Hello everyone, I am quick-frozen fish 🐟, a water front 💦, like the garish 💐, continuous sand sculpture 🌲 Welcome friends to add my wechat: Sudongyuer pull you into the group of my public number: front-end quick-frozen fish progress together, looking forward to growing together with everyone

Preface 🌧 ️

Algorithms are unfamiliar and familiar to the front-end people, and often we don’t value them as much as the back-end engineers do. But in fact, algorithms have an unshakable position for every programmer.

Because the development process is to convert the actual problem into the computer can recognize the instructions, that is, “data structure” said, “design the data structure, in the application of algorithms on the line”.

Of course, learning is also focused, as the front end we do not need to fully grasp the algorithm like back-end development, some of the more partial, not practical type and solution method, as long as a little understanding.

The title 🦀

Offer 14-i. Cut the rope

The difficulty of medium

You are given a piece of string of length n. Please cut the string into m segments of integer length (m and n are integers, n>1 and m>1). Write the length of each segment as K [0],k[1]… K (m – 1). K, please [0] [1] * * k… What is the largest possible product of k[m-1]? For example, when the length of the rope is 8 and we cut it into three lengths of 2, 3 and 3, the maximum product we get is 18.

Example 1:

Input: 2 Output: 1 Description: 2 = 1 + 1, 1 × 1 = 1Copy the code

Example 2:

Input: 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36Copy the code

Tip:

  • 2 <= n <= 58

🌵

  • This question to tell the truth, I really think about this brain for a long time, body and person, I am very sad (sad ~)
  • This problem can be solved by finding rules and DP dynamic programming, which is easier to understand
  • dp[i]What it means: Split the numbersi, the largest product can be obtained asdp[i]
  • Recursive formula: for some I, use j to traverse from 1 to i-1:
  • (i-j)*jIt is divided into two numbers
  • dp[i-j]*jIndicates the number divided into two or more
  • Because j is going to figure out a lot as we go throughdp[i], take the largest of the three
  • sodp[i] = Math.max(dp[i], (i - j) * j, dp[i - j] * j)
  • Dp [I] initialization: since the value of dp[I] needs to be compared each time, prevent the first comparison from beingundifined, initializes the dp array with length ofn+1Attach default values
  • Go back and forth

Source 🔥

/ * * *@param {number} n
 * @return {number}* /
var cuttingRope = function(n) {
    const dp=Array(n+1).fill(1)
    for(let i=2; i<=n; i++){for(let j=1; j<=i-1; j++){ dp[i]=Math.max(dp[i],dp[i-j]*j,j*(i-j))
        }
    }
    return dp[n]
};
Copy the code

Time complexity: O(N^2)

Space complexity: O(N)

Conclusion 🌞

So the “LeetCode” of the algorithm chapter refers to the offer-14-i cut the rope ⚡️. There is no shortcut to the algorithm, so we can only write and practice more and summarize more. The purpose of the article is actually very simple, which is to urge myself to complete the algorithm practice and summarize and output. I hope everyone can like my essay, and I also hope to know more like-minded friends through the article. If you also like to toss, welcome to add my friend, sand sculpture together, together progress.

Making 🤖 : sudongyu

Personal blog 👨💻: Frozen fish blog

Vx 👦 : sudongyuer

Write in the last

Guys, if you like my words, give 🐟🐟 a thumbs up 👍 or follow ➕ to support me the most.

Add me on wechat: Sudongyuer, invite you into the group and learning the front together, become a better engineer ~ (group of qr code here – > front to go to bed early, qr code has expired, see the links to the boiling point in the comments, I will put the latest qr code in the comments section, of course, can also add me WeChat I pull you into the group, after all, I also am interesting front end, I also not bad 🌟 ~