Leetcode -650- Keyboard with only two keys

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

Originally the notepad had A single character ‘A’. You can do two things with the notepad at a time:

Copy All: Copies All characters in this notepad (not only some characters). Paste: pastes the characters that were copied last time. Given the number n, you need to print exactly n ‘A’ in notepad using the minimum number of operations. Returns the minimum number of operations that can print n ‘A’.

Example 1:

Input: 3 Output: 3 Explanation: Initially, there is only one character 'A'. Step 1, use the Copy All operation. Step 2, use Paste to get 'AA'. Step 3, use the Paste operation to get 'AAA'.Copy the code

Example 2:

Input: n = 1 Output: 0Copy the code

Idea 1: Violent DFS

• We can record the current characters on the clipboard as well as the current characters
• Res++ for each additional operation
• There are two cases of operation
  • Copy the string on the clipboard
  • Updates the current string to the clipboard
• Both of these operations are res++
• There is no need to update the clipboard twice in a row.
• Since the maximum number of operations is n, we can define a maximum of 1010

class Solution {
    int target = 0, INF = 1010;
    public int minSteps(int n) {
     target = n;
     return dfs(1.0);
    }

    public int dfs(int cur, int paste){

            if(cur > target){
                return INF;
            }

            if(cur == target){
                return 0;
            }

            int res = INF;

            if(paste > 0){
                res= Math.min(res, dfs(cur + paste, paste));
            }


            if(cur ! = paste){ res= Math.min(res,dfs(cur,cur)); }return res+1; }}Copy the code

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

Idea 2: DFS + memorization

• The above solution clearly shows that there are two mutable elements, so it can be optimized using mnemonization
• Define the array memo[][]
• M [I][j] Records the minimum number of operations of j characters on the current I character clipboard

class Solution {
    int target = 0, INF = 1010;
    int[][] memo ;
    public int minSteps(int n) {
     target = n;
     memo =new int[n][n];
     return dfs(1.0);
    }

    public int dfs(int cur, int paste){
        if(cur > target){
            return INF;
        
        }
        if(cur == target){
            return 0;
        }
        if(memo[cur][paste]! =0) {return memo[cur][paste];
        }
        int res = INF;
        if(paste>0){
            res = Math.min(res, dfs(cur+paste,paste));
        }
        if(cur ! = paste){ res = Math.min(res, dfs(cur,cur)); } memo[cur][paste] = Math.min(res+1,memo[cur][paste]);
        return res+1; }}Copy the code

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

Idea 3: Dynamic planning

• We can think of a solution for DP already memorized
• [I][j]
• Represents the minimum number of schemes for the current I characters, j characters on the clipboard
• Initialization state
  • dp[1][0] = 0; dp[1][1] = 1;
  • [J] = INF;
• The transfer process
  • dp[i][j] = dp[i-j][j] + 1
  • At the same time, a minimum value min should be recorded to record the minimum value that reaches the current state, which is convenient to update the minimum number of operations that copy the current number of characters
  • min = Math.min(min,dp[i][j]);
  • The current dPI [I][I] indicates that the minimum value of the replication operation is DP [I][I] = min + 1

public int minSteps(int n) {
        int INF = 1010;
     int[][] dp =new int[n+1][n+1];
     for(int[] num:dp){
         Arrays.fill(num,INF);
     }
     dp[1] [0] = 0;
     dp[1] [1] = 1;
    for(int i = 2; i <=n; i++){int min = INF;
        for(int j = 0; j <= i/2; j++){
            dp[i][j] = dp[i-j][j]+1;
             min= Math.min(min, dp[i][j]);
        }
        dp[i][i] = min + 1;
    }
        int res = INF;
        for(int num:dp[n]){
            res = Math.min(res, num);
        }
        return res;
    }

Copy the code

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