Question

Задача на ДП:



Помогите плиз на с++ или джаве

Answer 1

Ответ:

Объяснение:

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <vector>

#include <queue>

#include <cstdio>

#include <algorithm>

#include <string>

#include <cmath>

#include <set>

using namespace std;

//#define int long long

int dp[1001][1001];

int main()

{

#ifdef _DEBUG

freopen("input.txt", "r", stdin);

#endif // _DEBUG

ios::sync_with_stdio(false);

cin.tie(0);

string a, b;

cin >> a >> b;

int s1 = a.size();

int s2 = b.size();

for (int i = 0; i < s1; i++)

{

 dp[i][0] = i;

}

for (int i = 0; i < s1; i++)

{

 dp[0][i] = i;

}

for (int i = 1; i <= s1; i++)

{

 for (int j = 1; j <= s2; j++)

 {

  dp[i][j] = dp[i - 1][j - 1];

  if (a[i - 1] != b[j - 1])

  {

   ++dp[i][j];

  }

  if (dp[i][j] > dp[i][j - 1] + 1)

  {

   dp[i][j] = dp[i][j - 1] + 1;

  }

  else if (dp[i][j] > dp[i - 1][j] + 1)

  {

   dp[i][j] = dp[i - 1][j] + 1;

  }

 }

}

cout << dp[s1][s2];

}