این سوال قبلا هم پرسیدم ولی کسی جواب نداده لطفا چواب بدید
فرض کنید X=X1X2...XM, Y=Y1Y2...YN دو رشته با ۴ الفبا باشند طولانی ترین زیر رشته مشترک LCS را حساب می کنیم برای محاسبه c[i,j] در بدتربن حالت جند خانه جدول بررسی می شود
جواب مقدار ۳ اعلام شده
می دانم که
اگر x1 = y1 انگاه c[i,j] = 1 + c[i-1,j-1
اگر x1 <> y1 انگاه c[i,j] = max(c[i-1,j],c[i,j-1
ولی با ابن حساب جواب ۲ نمبشه اگر x1 <> y1 باید دو خانه دیگر بررسی شوند
c(i-1,j-1)
c(i-1,j)
c(i,j-1)
این سه تا در بدترین حالت بررسی میشند...!
ممنون از جوابتان ولی متوجه نشدم همانطور که کفتم تعداد خانه های بررسی شونده منوط به براورده شدن شرط x1 = y1 یا عدم براورده شدن ان است
اگر x1 = y1 انگاه c[i,j] = 1 + c[i-1,j-1
اگر x1 <> y1 انگاه c[i,j] = max(c[i-1,j],c[i,j-1
اگر شرط براورده شود ۱ خانه وگرنه ۲ خانه بررسی می شوند