Join Us
Loading Similar Posts
Entering edit mode
string modification
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
string s;
int dp[100005][27][5];
int rec(int i, int prev, bool matched)
{
if (i >= n)
{
if (matched == 1)
return 1e17;
else
return 0;
}
if (dp[i][prev][matched] != -1)
return dp[i][prev][matched];
int ans = 1e17;
if (matched == 0)
{
int val = s[i] - 'a';
// cout << val << endl;
int cost = abs(prev - val);
ans = cost + rec(i + 1, prev, 1);
}
else
{
// int dum = 1e9;
for (int j = 0; j < 26; j++)
{
if (j == prev)
{
int val = s[i] - 'a';
int cost = abs(val - prev);
ans = min(ans, cost + rec(i + 1, prev, 1));
}
else
{
int val = s[i] - 'a';
int cost = abs(val - prev);
ans = min(ans, cost + rec(i + 1, prev, 0));
}
}
}
return dp[i][prev][matched] = ans;
}
int32_t main()
{
cin >> n;
cin >> s;
int ans = 1e17;
memset(dp, -1, sizeof(dp));
for (int i = 0; i < 26; i++)
{
int val = s[0] - 'a';
int cost = abs(val - i);
// cout << cost << endl;
ans = min(ans, cost + rec(1, i, 0));
}
cout << ans << endl;
return 0;
}
//there were some small mistakes in your code
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int dp[100005][27][5];
int rec(int i, int prev, int matched,int n,string &s) {
if (i >= n) {
if (matched) return 0;//if its matched we should return 0 else 1e9
else return 1e9;
}
if (dp[i][prev][matched] != -1) return dp[i][prev][matched];
int ans = 1e9;
if (matched == 0) {
int val = s[i] - 'a';
int cost = abs(prev - val);
ans = cost + min(rec(i + 1, prev, 1,n,s),rec(i + 1, val, 1,n,s)); // we can change the prev to val or val to prev so we should take min of those both
}else{
for (int j = 0; j < 26; j++) {
int val = s[i] - 'a';
if (j == prev) {
int cost = abs(val - prev);
ans = min(ans, cost + rec(i + 1, j, 1,n,s));
} else {
int cost = abs(val - j); // u did val -prev for everything
ans = min(ans, cost + rec(i + 1, j, 0,n,s));
}
}
}
dp[i][prev][matched] = ans;
return ans;
}
int main()
{
string s;
cin>>s;
int ans=1e9;
memset(dp, -1, sizeof(dp));
int n = s.size();
for (int i = 0; i < 26; i++) {
int val = s[0] - 'a';
int cost = abs(val - i);
ans = min(ans, cost + rec(1, i, 0,n,s));
}
cout << ans << endl;
return 0;
}