بزرگ‌ترین زیردنباله مشترک

Longest common subsequence

شرح مساله(ویکی پدیا) :

دو رشته زیر را در نظر بگیرید:

هدف مقایسه این دو رشته و پیدا کردن شباهت بین آنها است. بزرگترین زیردنباله مشترک این طور تعریف می‌شود که دنباله‌ای مانند است به طوری که حروف موجود در با حفظ ترتیب در و موجود باشد. اما مطلقاً لزومی ندارد که متوالی باشد. از طرفی باید بزرگترین دنباله ممکن با خواص بالا باشد. به طور کلی اگر دو رشته و را در نظر بگیریم٫ یک بلندترین زیر دنباله مشترک را می‌توان با استفاده از برنامه نویسی پویا پیدا کرد.

Project Euler Problem 31

صورت اصلی سوال : http://projecteuler.net/problem=31
ترجمه :
در انگلستان واحد پول بر پایه پند و پنس است .
(£1=100p)
در کل هشت نوع سکه وجود دارد : 1p, 2p, 5p, 10p, 20p, 50p, £1-100p and £2-200p
برای مثال می تونیم دو پند رو به شکل زیر درست کنیم :
1£1 + 150p + 220p + 15p + 12p + 31p

چند راه متفاوت برای ساختن 2 پند وجود به طوری از هر سکه به تعدادی نا محدود در اختیار داشته باشیم ؟

___________________________________________

شرح راه حل : مسئله را با بهره گیری از برنامه ریزی پویا حل می کنیم ...
کد راه حل : http://snipt.net/JahanaraCo/project-euler-problem-31