資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的迴文劃分 III
假設我們有一個字串 s，其中包含小寫字母和一個整數 k。我們必須維護一些屬性。這些是 -
- 首先，我們必須更改 s 的某些字元（如果需要）為其他小寫英文字母。
- 然後將字串 s 分割成 k 個子字串，使得每個子字串都是迴文。
我們必須找到我們需要更改的字元的最小數量以分割字串。
因此，如果字串類似於“ababbc”且 k = 2，則答案將為 1，因為我們必須更改一個字元才能將其分成兩個迴文字串。因此，如果我們將 c 更改為 b，或將倒數第二個 b 更改為 c，那麼我們可以得到一個迴文，例如“bbb”或“cbc”，另一個迴文是“aba”。
為了解決這個問題，我們將遵循以下步驟 -
- 定義一個大小為 105 x 105 的陣列 memo。
- 定義一個函式 solve()，它將接收 s、idx、k、一個二維陣列 > dp，
- 如果 idx 與 s 的大小相同，則 -
- 返回當 k 為 0 時為 0，否則為 1000
- 如果 memo[idx][k] 不等於 -1，則 -
- 返回 memo[idx][k]
- 如果 k <= 0，則 -
- 返回 inf
- ans := inf
- 對於初始化 i := idx，當 i < s 的大小時，更新（i 增加 1），執行 -
- ans := ans 和 dp[idx][i] + 呼叫函式 solve(s, i + 1, k - 1, dp) 的最小值
- 返回 memo[idx][k] = ans
- 從主方法中執行以下操作
- n := s 的大小
- 用 -1 填充 memo
- 定義一個大小為 n x n 的二維陣列 dp
- 對於初始化 l := 2，當 l <= n 時，更新（l 增加 1），執行 -
- 對於初始化 i := 0，j := l - 1，當 j < n 時，更新（j 增加 1），（i 增加 1），執行 -
- 如果 l 等於 2，則 -
- 當 s[i] 不等於 s[j] 時，dp[i][j] := true
- 否則
- 當 s[i] 等於 s[j] 時，dp[i][j] := dp[i + 1][j - 1] + 0
- 對於初始化 i := 0，j := l - 1，當 j < n 時，更新（j 增加 1），（i 增加 1），執行 -
- 返回 solve(s, 0, k, dp)
讓我們看看以下實現以獲得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int memo[105][105];
lli solve(string s, int idx, int k, vector < vector <int> > &dp){
if(idx == s.size()) {
return k == 0? 0 : 1000;
}
if(memo[idx][k] != -1) return memo[idx][k];
if(k <= 0)return INT_MAX;
lli ans = INT_MAX;
for(int i = idx; i < s.size(); i++){
ans = min(ans, dp[idx][i] + solve(s, i + 1, k - 1, dp));
}
return memo[idx][k] = ans;
}
int palindromePartition(string s, int k) {
int n = s.size();
memset(memo, -1, sizeof(memo));
vector < vector <int> > dp(n, vector <int>(n));
for(int l =2; l <= n; l++){
for(int i = 0, j = l - 1; j <n; j++, i++){
if(l==2){
dp[i][j] = !(s[i] == s[j]);
}else{
dp[i][j] = dp[i+1][j-1] + !(s[i] == s[j]);
}
}
}
return solve(s, 0, k, dp);
}
};
main(){
Solution ob;
cout << (ob.palindromePartition("ababbc", 2));
}輸入
“ababbc”
輸出
1
更新於: 2020年6月2日
151 次檢視
廣告