مقدمه
 بعد از اینکه Dynamic Programming را به صورت کلی مورد بازبینی قرار دادیم. طبق قراری که گذاشته شد در این مطلب و مطالب بعدی به توضیح بیشتر در این زمینه میپردازیم.
بد نیست بدانید که برنامه نویسی پویا دارای یک سری مسئله کلیشه مانند:

  • کولپشتی صفر و یک 01 Knapsack
  • کوله پشتی Knapsack
  • طولانی ترین زیر آرایه همسان Longest Common Sequence
  • طولانی ترین زیر آرایه صعودی Longest Increasing Sequence

می باشد. برای این مسائل به حد کافی آموزش در اینترنت وجود دارد توصیه میشود که این مطالب را به عنوان تمرین بیشتر مطالعه کنید.
این مطلب در مورد حل مسئله RNA Molecules مسابقه ملی اینترنتی 2013 سایت شریف  با استفاده از تکنیک برنامه نویسی پویا میباشد. 


متن سوال
کلیه سوالات 11 امین مسابقه ملی ACM
ورودی و خروجی ها
این مسئله سوال C مسابقه بود همینطور که میبینید.


حل
خب ما میبایست در یک رشته ماکزیمم جفت های (A,U)،(U,A)،(G,C)،(C,G) را بیابیم که بیشتر از 2 حرف فاصله داشته باشند.
بعد از دریافت رشته دو حرف چپ و راست رشته را بررسی میکنیم. آیا با الگو برابر بود ؟ در اینصورت یکی از جواب های ما تابع با ورودی همین رشته بدون این 2 حرف هست به علاوه یک.
حال یکبار به این رشته بدون حرف سمت چپ و بدون حرف سمت راست نگاه میکنیم. دو جواب جدید پیدا شد.


هنوز راه حل ما کامل نیست. به ازای ورودی مثل CGGGUUUA که دارای جواب 2 میباشد. برنامه ما به طور اشتباه یک خروجی میدهد.
یا به عبارت دیگر توان پیدا کردن جفت های کنار هم را ندارد و تنها میتواند به صورت داخلی ماکزیمم را پیدا کند.
این مشکل را میتوانیم بایک برش در رشته حل کنیم. و هربار برای هر یک از دو قطعه ای که ایجاد میشوند تابع را صدا بزنیم و یک جواب که برابر با مجموع جواب این دو زیر مسئله است داشته باشیم.
و از اینجا هم اگر طول رشته را N در نظر بگیریم. N-1 جواب داریم .


برای پیدا کردن جواب کافیست بین این جواب های بدست آمده جواب ماکزیمم را پیدا کنیم.


ممکن است این سوال پیش بیاید که شاید به بیش از یک برش در رشته نیاز باشد؟ بله این ادعا درست است اما میتوان براحتی اثبات کرد که برای N برش هم این راه حل درست میباشد.


با صدا زدن زیر مسئله مشخص شد که این یک مسئله بازگشتی میباشد.
چون مقدار ماکزیمم برای زیر رشته L  تا R یک مقدار ثابت میباشد. میتوانیم این مقدار که ممکن است چندین بار مورد استفاده قرار بگیرد را ذخیره کنیم تا از بررسی دوباره آن جلو گیری کنیم.


بدون انجام دادن تکنیک برنامه نویسی پویا راه حل بالا در محدوده زمانی مورد نظر به جواب نمیرسد و مورد قبول نیست.


در زیر کد این راه حل را به زبان C++ مشاهده میکنید.

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
#define MAXN 501
int DP[MAXN][MAXN];
string s;
int n;
int getMax(int l,int r){
	if(l<0||r>=n)return 0;
	if(r-l<2)return DP[l][r]=0;
	if(DP[l][r]!=-1)return DP[l][r];
	int i,j,mmax,add=0;
	if(s[l]=='A'&&s[r]=='U')add=1;
	else if(s[l]=='U'&&s[r]=='A')add=1;
	else if(s[l]=='G'&&s[r]=='C')add=1;
	else if(s[l]=='C'&&s[r]=='G')add=1;
	mmax=add;
	mmax=max(mmax,getMax(l+1,r-1)+add);
	mmax=max(mmax,getMax(l+1,r));
	mmax=max(mmax,getMax(l,r-1));
	for(i=l;i<r;i++){
		mmax=max(mmax,getMax(l,i)+getMax(i+1,r));
	}
	return DP[l][r]=mmax;
}
int main(){
	int mmax,i,j;
	while(cin>>n&&n){
		memset(DP,-1,sizeof(DP));
		cin>>s;
		cout<<getMax(0,n-1)<<endl;
	}
	return 0;
}