2 Problem (Dynamic Programming)

Q1:Longest Increasing Subsequence( only find the length)

Core formula as below:

Pseudo-code as below:

OPT(A[1]) = 1;  // OPT(A[i]) stores the length of substring including A[i]

value = OPT(A[1]); // value stores the max OPT(A[1..i])

while A[i+1] is not the end

if (A[i+1] <= A[i])

OPT(i+1) = 1;

else

OPT(i+1) = Max{ OPT(i), value } + 1;

endif

if (OPT(i+1) >= value)

value = OPT(i+1);

endif

i++;

end while  // value is the result of length of longest increasing substring

Q2: Solution to find the length of longest palindrome in a string can be as followed.

Converse the original string to a new one and find the longest common subsequence of these two strings.

Core formula:

little code:

#include<iostream>
#include<string>
using namespace std;

int max(int a,int b)
{
	if(a<b)
		return b;
	else
		return a;
}

int main()
{
	cout<<"input your string:"<<endl;
	string str;
	cin>>str;
	int n=int(str.length());
    string constr(str.rbegin(),str.rend());;
	int **opt=new int*[n];
	for(int i=0;i<n;i++)
	{
		opt[i]=new int[n];
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			opt[i][j]=0;
		}
	}
    // initialization
    if(str[0] == constr[0])  // after debug
    {
        for(int j=0; j<n; j++)
            opt[0][j] = 1;
        for(int i=0; i<n; i++)
            opt[i][0] = 1;
    }
    else{
        for(int j=1; j<n; j++)
            if(str[0] == constr[j])
                opt[0][j] = 1;
        for(int i=1; i<n; i++)
            if (str[i] == constr[0])
                opt[i][0] = 1;
    }
    //core formula
	for(int i=1;i<n;i++)
	{
		for(int j=1;j<n;j++)
		{
			if(str[i]==constr[j])
				opt[i][j]=opt[i-1][j-1]+1;
			else
				opt[i][j]=max(opt[i-1][j],opt[i][j-1]);
           // printf("opt[%d][%d] =%d\n ",i,j,opt[i][j]);
		}
	}
	cout<<"max length: "<<opt[n-1][n-1]<<endl;
	for(int i=0;i<n;i++)
	{
		delete[] opt[i];
	}
	delete[] opt;
	return 0;
}