چطور میشه بزرگترین زیر دنباله مشترک بین این رشته هارو پیدا کرد مثلا
با روش پویا احتمالا باید حل بشه ولی ممنون میشم راهنمایی کنید
الگوریتم خاصی داره؟
۲,۱۱,۳,۱۰,۸,۶,۷,۹,۱,۴,۵
۱,۲,۳,۴,۵,۶,۷,۸,۹,۱۰,۱۱
(۱۷ خرداد ۱۳۹۵ ۱۱:۴۲ ب.ظ)kamal3401 نوشته شده توسط: چطور میشه بزرگترین زیر دنباله مشترک بین این رشته هارو پیدا کرد مثلا
با روش پویا احتمالا باید حل بشه ولی ممنون میشم راهنمایی کنید
الگوریتم خاصی داره؟
۲,۱۱,۳,۱۰,۸,۶,۷,۹,۱,۴,۵
۱,۲,۳,۴,۵,۶,۷,۸,۹,۱۰,۱۱
آره داینامیک میخواد.
فرض کن [tex]a=(a_1,\: a_2,\: ...,\: a_n)[/tex] یک رشته، و یکی دیگه [tex]b=(b_1,\: b_2,\: ...,\: b_m)[/tex] باشه
اگه دو تای سمت راست باهم برابر باشند، قطعاً در زیردنباله باید باشند (و الا زیردنباله ماکزیمم نیست).
پس در [tex]a=(a_1,\: a_2,\: ...,\: a_{n-1})[/tex] و [tex]b=(b_1,\: b_2,\: ...,\: b_{m-1})[/tex] دنبال مابقی بگردیم.
ولی اگر برابر نباشند یا در [tex]a=(a_1,\: a_2,\: ...,\: a_{n-1})[/tex], [tex]b=(b_1,\: b_2,\: ...,\: b_{m})[/tex] و یا در [tex]a=(a_1,\: a_2,\: ...,\: a_{n})[/tex], [tex]b=(b_1,\: b_2,\: ...,\: b_{m-1})[/tex] هست.
ضمنا نمیتونیم هر دو کاراکتر آخری رو حذف کنیم چون ممکن هست یکی توو زیردنباله‌ی مشترک باشه (یعنی اینکه کاراکترهای آخر با هم برابر نیستند معنی این رو نمیده که هیچ کدوم در زیردنباله نیستند، به این معنی هست که "هر دو با هم نیستند" و ممکن هست یکی باشه).
لذا
[attachment=20021]