Assalomu alaykum, yordam.uz saytimizga xush kelibsiz.
Bu saytda o`zingizni qiziqtirgan savollarga javob olishingiz va o`z sohangiz bo`yicha savollarga javob berishingiz mumkin. Bizning Oilamizga a'zo bo`lganingiz uchun chuqur Minnatdorchilik bildiramiz !!!

Qavslarni qayta tiklash

+3 ovoz
73 marta ko‘rilgan
so‘radi 07 yanvar, 17 abdujabbor (399 bal)
tahrirlandi 07 yanvar, 17 Saidolim

Quyidagi algoritmni yaxshi tushunolmadim to'liqroq o'zbek tilida tushuntirib berolasilarmi?

Число действий для восстановления скобок вставкой

Дана строка S, состоящая из круглых, квадратных и фигурных скобок. Определить минимальное количество символов, которые требуется добавить в строку S, чтобы получилась правильная скобочная последовательность.

Вид подзадачи: d[i][j] — минимальное количество символов, которые требуется добавить в подстроку S[i..j], чтобы получилась правильная скобочная последовательность.

Рекуррентная формула: d[i][j] = min(d[i][k] + d[k + 1][j]), где k ∈ i..(j - 1); если S[i] и S[j] — соответствующие открывающая и закрывающая скобки, то d[i][j] = min(d[i][j], d[i + 1][j - 1]).

База рекурсии: d[i][i] = 1; если i < j, то d[i][j] = 0.

Вид ответа: d[0][n - 1]. Сложность O(N^3).

TAHRIR:

Qo`shish yordamida qavslarning mosligini tiklash uchun amallar soni

S satr berilgan. Satr dumaloq, to`rtburchak va shaklli qavslardan iborat. 

S satrga qaslarning to`g`ri ketma-ketligi hosil bo`lishi uchun qo`shilishi kerak bo`lgan eng kam belgilar sonini aniqlang.

Masala ichida masala: d[i][j] -  S satrda qavslar to`g`ri ketma-ketlikda bo`lishini ta'minlobchi, S[i..j]ga qo`lishili kerak eng kam belgilar soni.

Rekurent funksiya: d[i][j] = min(d[i][k] + d[k + 1][j]),
bu yerda k ∈ i..(j - 1); agar S[i] и S[j] - mos ravishdagi ochiluvchi va yopiluvchi qavslar belgilari. 
u holda d[i][j] = min(d[i][j], d[i + 1][j - 1]) bo`ladi.

Rekursiya asosdi : d[i][i] = 1; agar i < j, u holda d[i][j] = 0.

Javob shakli: d[0][n - 1]. 

Murakkablik O(N3).

izoh qoldirdi 07 yanvar, 17 Saidolim (3,546 bal)
savol o`zbek tilida bo`lishi kerak ediku )))

Iltimos, saytga kiring yoki ro‘yxatdan o‘ting va shunda ushbu savolga javob berishingiz mumkin bo‘ladi.

Assalomu alaykum, yordam.uz saytimizga xush kelibsiz.

Bu saytda o`zingizni qiziqtirgan savollarga javob olishingiz va o`z sohangiz bo`yicha savollarga javob berishingiz mumkin.

Bizning Oilamizga a'zo bo`lganingiz uchun chuqur Minnatdorchilik bildiramiz !!!

Telegram kanal YordamUzRss

...