This is the 22nd day of my participation in the August More Text Challenge

One, foreword

Hello, everyone. This is the 11th article in a series called “Offer of the Day”.

In this series of articles, I will review the data structure and algorithm basis by brushing questions for practice, and I will also share my brushing process in the form of blog. If you happen to want to brush up on algorithms, encourage each other to learn. My algorithm foundation is weak, and I hope to make up for this loophole in the next two or three months. The language used for this brush is Java, and it is expected that Python will be used for the second brush.

  • Leetcode’s key Offer topic
  • Code cloud warehouse address

Second, the subject

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). Excuse me [1] [0] k 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

Third, the problem solving

3.1 Idea 1: Dynamic planning

The rope cut must be divided into at least two sections, that is, the rope of length N must have n-1 choice after the first cut, so f(n) = Max (f(I) * f(n-i)).

This is a top-down recursive formula, and because recursion has many repeating sub-problems, it causes a lot of unnecessary double computation.

Therefore, we use an array DP to hold the maximum of these lengths.

  • DP[1] = 1
  • DP[2] = 1* 2 = 2
  • DP[3] = 1*3 = 3
  • DP[4] = 2*2 = 1 * 4 =4
  • DP[n] = DP[i] * DP [n-i]

However, it is important to note that if the length of the rope is less than 4, then it has to be divided by two cuts, so there are no DP values, because it has to be divided, so these values are treated specially, and then the length of the rope is greater than or equal to 4.

3.1.1 code

In this code, the optimal solutions to the subproblems are stored in the DP array and the I of the for loop is sequentially increasing, which means that the order of computation is bottom-up.

    int [] dp =new int[n+1];
         if(n<=2)
             return 1;
         if(n==3)
             return 2;
         dp[1]=1;
         dp[2]=2;
         dp[3]=3;
         for (int i = 4; i <=n; i++) {
             for (int j = 1; j <=(i / 2); j++) {
                 dp[i]=Math.max(dp[i],dp[j]*dp[i-j]);
             }
         }
         return dp[n];
Copy the code
3.1.2 Execution Effect

3.1.3 complexity
  • Time complexity: O(n ^ 2)
  • Space complexity: O(n)

3.2 Idea 2: Greedy algorithm

The idea is: when n is greater than 4, divide the rope into 3 pieces as much as possible, so that the product is maximum.

Mathematical proof, see k god: leetcode-cn.com/problems/ji…

  • If n == 2, return 1, if n == 3, return 2, the two can be combined to return n-1 if n is less than 4
  • If n == 4, return 4
  • If n > 4, divide into as many segments of length 3 as possible, the length of each cycle n minus 3, the product res multiplied by 3; And then it returns times the last bit that is less than or equal to 4
  • The above 2 and 3 can be combined
3.2.1 code
public class Number11_2 { public static void main(String[] args) { System.out.println(cuttingRope(5)); } public static int cuttingRope(int n) { int [] dp =new int[n+1]; if(n<4) return n-1; int res=1; while (n>4){ res*=3; n-=3; } return res*n; }}Copy the code
3.2.2 Execution Effect

3.2.3 complexity
  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)

Four,

This paper makes a preliminary study of dynamic programming and greedy algorithm, hoping readers can use dynamic programming problem flexibly to solve such flexible problems, and greedy algorithm also needs mathematical foundation.