資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學移除由單個不同字元組成的子字串可能獲得的最大分數
移除由單個不同字元組成的子字串可能獲得的最大分數是計算機科學和演算法設計領域的一個著名問題。問題陳述涉及找到從僅包含一種字元型別的二進位制字串中移除所有連續子字串的最佳解決方案，併為每個長度為 K 的移除子字串獲得分數，其中 K 對於每個子字串可能不同。這個問題在文字分析和壓縮等各種現實生活中都有應用。
在本教程中，我們將使用 C++ 提供此問題的解決方案，並解釋我們演算法背後的邏輯。我們還將討論解決方案的時間和空間複雜度，並提供一個關於如何實現它的分步指南。讓我們開始吧！
問題陳述
這個問題需要找到透過從二進位制字串 S 中刪除任意長度的連續子字串可以達到的最高分數，其中每個刪除的子字串只包含相同的字元。大小為 N 的陣列 A 包含每個長度子字串的分數，長度為 K 的刪除子字串的分數為 A[K]。
示例 1
輸入
A binary string S is given as "abb" and an array A is given as [2, 3, 1].
輸出
A score of 6 can be achieved by removing substrings composed of identical characters, resulting in the maximum attainable score.
解釋：最初，分數為 0，字串為“abb”，我們刪除索引 2 處的子字串（長度為 1），並將分數增加陣列中的相應值。結果，字串變為“ab”，分數增加到 1。接下來，我們刪除索引 1 處的子字串，將其相應的值新增到分數中，並將字串修改為“a”。然後分數變為 4。最後，我們刪除索引 0 處的子字串，將其相應的值新增到分數中，並將字串更新為空字串。最終分數為 6。
示例 2
輸入
A binary string S is given as "abb" and an array A is given as [1, 3, 1].
輸出
A score of 4 can be achieved by eliminating substrings composed of identical characters, resulting in the maximum possible score.
解釋：從分數 0 開始，初始字串“abb”經歷子字串移除。具體來說，移除子字串“bb”，將陣列 A 中的相應值新增到分數中，導致修改後的字串“a”和分數 3。隨後，移除剩餘的字元“a”，將 A[1] 新增到分數中，導致空字串和最終分數 4。此過程舉例說明了程式如何透過戰略性地從輸入字串中移除子字串來計算可以達到的最大分數。
演算法
1. 從包含必要的標頭檔案開始：“iostream”、“vector”、“map”和“algorithm”。
2. 宣告一個名為“dp”的“std::map”來儲存預先計算的結果。
3. 定義一個名為“calculateMaximumScore”的函式，該函式接受字串“str”和整數向量“nums”作為輸入並返回一個整數。
4. 在“calculateMaximumScore”函式中
檢查“dp”對映中是否存在字串“str”。如果找到，則返回相應的值。
計算輸入字串“str”的長度並將其儲存在變數“len”中。
如果字串的長度為 0，則返回 0。
如果字串的長度為 1，則返回“nums”向量的第一個元素。
將變數“start”初始化為 0，將“maxScore”初始化為 -1。
以“start”作為迴圈變數啟動一個迴圈，並在“start”小於“len”時迭代。
在迴圈中，將另一個變數“end”初始化為“start”。
以“end”作為迴圈變數啟動一個內部迴圈，並在“end”小於“len”時迭代。
檢查索引“end”處的字元是否與字串“str”中索引“start”處的字元不同。
透過從字串“str”中提取從索引“start”到索引“end”的字元來建立一個子字串“sub”。
透過將“nums”向量中索引“sub.size() - 1”處的值與在分別連線“start”和“end”之前和之後的子字串上遞迴呼叫“calculateMaximumScore”函式的結果相加來計算最大分數。
使用當前“maxScore”和計算出的分數的最大值更新“maxScore”。
將“end”遞增 1。
檢查“end”是否等於“len”。如果是，則退出外迴圈。
將“start”遞增 1。
宣告一個字串變數“inputStr”並將其初始化為輸入字串“abb”。
宣告一個整數向量“inputNums”並將其初始化為輸入值{2, 3, 1}。
使用“inputStr”和“inputNums”作為引數呼叫“calculateMaximumScore”函式，並輸出結果。
5. 在“main”函式中
該演算法概述了程式根據給定的輸入字串和數字向量計算最大分數時執行的步驟。
示例
使用 C++ 實現上述演算法
下面的 C++ 程式實現了一種動態規劃方法來計算從給定字串中移除子字串後可以達到的最大分數。它利用記憶化來儲存預先計算的結果，並透過將問題分解成更小的子問題來最佳化遞迴。透過迭代地檢查不同的子字串，它透過考慮每個子字串的移除並遞迴地計算修改後的字串的分數來確定最大分數。
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
std::map<std::string, int> dp;
int calculateMaximumScore(std::string str, std::vector<int> nums) {
if (dp.find(str) != dp.end()) {
return dp[str];
}
int len = str.size();
if (len == 0) {
return 0;
}
if (len == 1) {
return nums[0];
}
int start = 0;
int maxScore = -1;
while (start < len) {
int end = start;
while (end < len) {
if (str[end] != str[start]) {
start = end;
break;
}
std::string sub = str.substr(start, end - start + 1);
maxScore = std::max(maxScore, nums[sub.size() - 1] +
calculateMaximumScore(str.substr(0, start) +
str.substr(end + 1), nums));
end += 1;
}
if (end == len) {
break;
}
}
dp[str] = maxScore;
return maxScore;
}
int main() {
std::string inputStr = "abb";
std::vector<int> inputNums = {2, 3, 1};
std::cout << "The maximum score possible by removing substrings made up of single distinct character: " << calculateMaximumScore(inputStr, inputNums);
return 0;
}
輸出
The maximum score possible by removing substrings made up of single distinct character: 6
結論
總而言之，提供的 C++ 程式有效地計算了從給定字串中移除由單個不同字元組成的子字串後可以達到的最大分數。透過使用動態規劃方法和記憶化，程式透過儲存預先計算的結果來最佳化計算。透過遞迴地探索不同的子字串，程式透過考慮每個子字串的移除並選擇最高得分路徑來確定最佳分數。該程式為透過智慧地從輸入字串中移除子字串來最大化分數提供了一個強大的解決方案。
209 次瀏覽
