Topic describes

Their thinking

  • Max = “BigInt”; Max = “BigInt”; Max = “BigInt”; Max = “BigInt”; In this case, we use the sorting method to find the maximum value, but the sorting method is particular, see the following solution code

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
    // In this case, there is a default condition: n is greater than or equal to 2
    const dp = new Array(n + 1);
    dp.fill(BigInt(1));
    for (let i = 3; i < dp.length; i++) {for (let j = 1; j < i; j++) { dp[i] = max(dp[i],BigInt(j*(i-j)),BigInt(j)*dp[i-j]); }}return dp[n] % 1000000007n
    function max(. args) {
        args.sort((a, b) = > (a < b) ? -1 : ((a > b) ? 1 : 0));
        return args[2]; }};Copy the code

Conclusion (this topic gives us the enlightenment of thinking)

  • Learn how to solve rope cutting problems with the idea of dynamic programming.
  • Learn to use BigInt.
  • Learn to sort by using sort to compare sizes.

reference

Sword point to Offer — cut string (JS implementation)