مشکل در طراحی الگوریتم

[aliexo]

به یکی از دوستام یک پروژه دادن،قراره من بنویسم براش اما اطلاعات کافی در مورد راه حلش و نوشتن کدش ندارم
کسی می تونه کمک کنه؟راه حلی الگوریتمی چیزی
می خواهم به زبان c++ یا #C بنویسم
لطفا کمک کنید





دو رشته از حروف به صورت X=x1x2...xn و Y=y1y2...ym داده شده است. می‌خواهیم با اجرای اعمال ویرایشی رشته X را به رشته Y تبدیل کنیم به گونه‌ای که مجموع هزینه اعمال انجام شده کمترین باشد. برنامه باید کمترین هزینه تبدیل لازم را بدست آورد. اعمال ویرایشی مجاز عبارت است از:

الف) حذف یک حرف از رشته، باز هزینه d

ب) اضافه کردن یک حرف در رشته با هزینه I

ج) تعویض کردن یک حرف در یک رشته با یک حرف دیگر با هزینه C



برای مثال چنانچه X=abbac و Y=abcb باشد و هزینه اجرای کلیه اعمال ویاریشی را برابر در نظر بگیریم با اجرای سه عمل تبدیل به صورت زیر انجام خواهد شد.
abbac -> abcbac -> abcbc -> abcb

راهنمایی:

ماتریسی برای ثبت هزینه تبدیل i حرف اول از رشته X به j حرف اول از رشته Y تعریف کنید و برای آن رابطه‌ای بر اساس تبدیل تعداد کمتری از حروف (مثلا از روی C[i-1][j] ) در حالات مختلف بیابید.
C[i][j] = ?

به عنوان مثال اگر j=0 باشد در این صورت C[i][j] = i*d خواهد بود.