移动最小二乘_最小移动以形成弦

迷南。 2023-03-05 11:56 15阅读 0赞

移动最小二乘

**Problem statement:**

**问题陈述：**

Given a string ***S***, write a program to check if it is possible to construct the given string ***S*** by performing any of the below operations any number of times. In each step, you can:

给定字符串***S*** ，编写一个程序以检查是否可以通过多次执行以下任何操作来构造给定的字符串***S。*** 在每个步骤中，您可以：

1.  Add any character at the end of the string.
    
    在字符串末尾添加任何字符。
2.  Append the existing string to the string itself.
    
    将现有字符串追加到字符串本身。

The above steps can be applied any number of times. We need to print the minimum steps required to form the string.

以上步骤可以应用多次。 我们需要打印形成字符串所需的最少步骤。

**Input:**

**输入：**

Input String

输入字符串

**Output:**

**输出：**

Minimum number of steps required to form that string.

形成该字符串所需的最少步骤数。

**Constraints:**

**限制条件：**

1 <= string length <= 10^5

**Example:**

**例：**

Input:
    aaaaaaaa 
    
    Output:
    4
    
    Explanation:
    Move 1: add 'a' to form "a"
    Move 2: add 'a' to form "aa"
    Move 3: append "aa" to form "aaaa"
    Move 4: append "aaaa" to form "aaaaaaaa"
    
    Input:
    ijhijhi
    
    Output:
    5
    
    Explanation:
    Move 1: add 'i' to form "i"
    Move 2: add 'j' to form "ij"
    Move 3: add 'h' to form "ijh"
    Move 4: append "ijh" to form "ijhijh"
    Move 5: add 'i' to form "ijhijhi"

**Solution Approach:**

**解决方法：**

So, we have two option

因此，我们有两种选择

1.  Append single character
    
    附加单个字符
2.  Append the string itself
    
    附加字符串本身

So, say the string is

所以说这个字符串是

x1x2 ... xn

For any sub-problem of size ***i***,

对于任何大小为***i的***子问题，

x1x2 ... xi

Two things are possible,

有两种可能

1.  Appends xi to sub-problem x1x2 ... x(i-1)
    
    将x i附加到子问题x 1 x 2 ... x (i-1)
2.  Append x1..xj to x1..xj is x(j+1)..xi is similar to x1..xj
    
    将x 1 ..x j追加到x 1 ..x j是x (j + 1) ..x i类似于x 1 ..x j

So, we can formulate the problem recursively,

因此，我们可以递归地提出问题，

f(i) = minimum steps to form x1x2 ... xi  
    f(i) = f(i-1)+1
    f(i) = f(j)+1 if j=i/2 and the partitioned strings are same

Now find the minimum.

现在找到最小值。

The base value of *f(i)=i* obviously which is maximum value to form the string.

*f(i)= i*的基值显然是构成字符串的最大值。

So, the above recursion can be transformed to DP.

因此，上述递归可以转换为DP。

1)  Declare int dp[n+1];
    2)  Assign the base value.    
        for i=0 to n
            dp[i]=i;
    3)  Fill the DP array
        for i=2 to n
            dp[i]=minimum(dp[i-1]+1,dp[i]); // normal insertion, recursion first case
            if i is even
                if s1s(i/2) = s(i/2+1)sn // if appending string is possible
                    dp[i]=minimum(dp[i],dp[i/2]+1);
            end if
        end for
        
    4)  return dp[n];
    
    DP[n] is the final result

**C++ Implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    int minimumMoves(string s)
    {
        int n = s.length();
    
        int dp[n + 1];
        for (int i = 0; i <= n; i++)
            dp[i] = i;
    
        for (int i = 2; i <= n; i++) {
            dp[i] = std::min(dp[i - 1] + 1, dp[i]);
            if (i % 2 == 0) {
                int flag = 0;
                for (int j = 0; j < i / 2; j++) {
                    if (s[j] != s[j + i / 2]) {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0)
                    dp[i] = std::min(dp[i], dp[i / 2] + 1);
            }
        }
    
        return dp[n];
    }
    
    int main()
    {
        cout << "Enter input string\n";
        string s;
        cin >> s;
        
        cout << "Minimum steps to form te string: " << minimumMoves(s) << endl;
    
        return 0;
    }

**Output:**

**输出：**

Enter input string
    incinclude
    Minimum steps to form te string: 8

> 翻译自: [https://www.includehelp.com/icp/minimal-moves-to-form-a-string.aspx][https_www.includehelp.com_icp_minimal-moves-to-form-a-string.aspx]

移动最小二乘

[https_www.includehelp.com_icp_minimal-moves-to-form-a-string.aspx]: https://www.includehelp.com/icp/minimal-moves-to-form-a-string.aspx