leetcode 650. 2 keys keyboard with only two keys (medium)

One 、 The main idea of the topic

label :  Dynamic programming

https://leetcode.cn/problems/2-keys-keyboard

At first, there was only one character in the Notepad  'A' . You can do two things with this notebook at a time ：

Copy All（ Copy all ）： Copy all the characters in this Notepad （ Copying only partial characters is not allowed ）.Paste（ Paste ）： Paste   Last time   Copied characters . Here's a number  n , You need to use the least number of operations , Output... In Notepad   just  n  individual  'A' . Return to print out  n  individual  'A'  The minimum number of operations .

Example  1：

Input ：3 Output ：3 explain ： first ,  There is only one character  'A'. The first  1  Step ,  Use  Copy All  operation . The first  2  Step ,  Use  Paste  Operation to get  'AA'. The first  3  Step ,  Use  Paste  Operation to get  'AAA'.

Example  2：

Input ：n = 1 Output ：0

Tips ：

• 1 <= n <= 1000

Two 、 Their thinking

Or dynamic programming , Here you need to multiply and divide to calculate the position , Because the paste operation is increased by digits . We use a one-dimensional array dp, And the location i Indicates extension to length i The minimum number of operations . For each location j, If j Can be i to be divisible by , So the length i It can be determined by the length j Operate to get , The number of operations is equivalent to a length of 1 Of A Extended to a length of i/j. So we can get the recurrence formula dp[i] = dp[j] + dp[i/j].

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
 public int minSteps(int n) {
 int[] dp = new int[n + 1];
 int h = n * n;
 for (int i = 2; i <= n; i++) {
 dp[i] = i;
 for (int j = 2; j <= h; j++) {
 if (i % j == 0) {
 dp[i] = dp[j] + dp[i / j];
 break;
 }
 }
 }
 return dp[n];
 }
}


Four 、 Summary notes

• 2022/7/2  expect 7 month 11 Number