1

动态编程DP：生成连续“XYZ”子字符串的最小插入量

 8 months ago
source link: https://www.jdon.com/71216.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

动态编程DP：生成连续“XYZ”子字符串的最小插入量

给定字符串S仅由字符 ' X'、' Y'和'Z'组成。您的任务是找到使字符串仅包含连续的“ XYZ ”子字符串所需的最少操作数，前提是您可以选择三个字符中的任何一个并将其插入S中的任何位置。

输入： S = XXX
输出： 6
解释：在最佳位置插入 3 个 Y 和 Z。这样S就变成= X YZ X YZ X YZ。现在，S 只包含连续的 XYZ 子串。因此，我们总共在 6 次操作中插入了 6 个字符（3 次 Y + 3 次 Z）。因此，输出为6。

输入： S = Y
输出： 2
解释：可以验证只需要2 次操作即可满足问题约束。

为了解决这个问题，您可以迭代给定的字符串并计算形成连续的“XYZ”子字符串所需的插入次数。

下面是一个实现此功能的 Python 函数：

def min_insertions_for_consecutive_xyz(s):
    count = 0
    i = 0

while i < len(s):
        if s[i:i+3] != 'XYZ':
            count += 1
            i += 1
        else:
            i += 3

return count

# Example usage:
input_string = "XAYBZC"
result = min_insertions_for_consecutive_xyz(input_string)
print("Minimum insertions:", result)

此函数min_insertions_for_consecutive_xyz接受字符串s作为输入，并返回生成连续“XYZ”子字符串所需的最小插入次数。
它使用 while 循环来迭代字符串，检查每个位置是否存在“XYZ”。

  • 如果未找到“XYZ”，则会增加计数并移至下一个字符。
  • 如果找到“XYZ”，它将跳过接下来的两个字符（因为“XYZ”已经是连续的子字符串）并继续检查字符串的其余部分。

算法角度
这个问题有一个默认上下文：可以选择在任何位置插入字符，那么，可以使用动态编程DP来解决这个问题。

动态编程DP：
动态编程主要是对普通递归的优化。无论何时我们看到重复调用相同输入的递归解决方案，我们都可以使用动态编程对其进行优化。
这个想法是：简单地存储子问题的结果，这样我们就不必在以后需要时重新计算它们。（类似缓存 思路）
这种简单的优化将时间复杂度从指数降低到多项式。

这个问题在DP中的主要概念是：

  • DP[X]会存储使字符串 S 的前 X 个字符仅包含子字符串 XYZ 的最少操作。
  • DP i = DP i + DP i -1 – 1（如果 S i > S i-1）
  • DP i = DP i + DP i-1 + 2 （否则）

C++实现：

// C++ code to implement the approach
include <bits/stdc++.h>
using namespace std;

// 将 xyz 类型字符串最小化的函数
int minimumOperations(string S, int N)
{
    // 以 0 开头的 DP 缓存中间结果
    vector<int> DP(N, 0);

// base case
    DP[0] = 2;

// 计算第 i 个状态的答案
    for (int i = 1; i < N; i++) {
        if (S[i] > S[i - 1])

// 最后一个字符的类型可以是
            // xy、yz、xz
            DP[i] = DP[i - 1] - 1;
        else
            // 或是x, y or z
            DP[i] = DP[i - 1] + 2;
    }

// Returing answer
    return DP[N - 1];
}

// Driver Function
int32_t main()
{

// Input
    int N = 2;
    string S = "XY";

// Function Call
    cout << minimumOperations(S, N) << endl;

return 0;
}

输出
1
时间复杂度： O(N)
辅助空间： O(N)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK