动态规划（生兔子问题 最长公共子序列）

动态规划（最长公共子序列）

int LCSLength(const char* X,const char* Y,int m,int n)
{
	if(m==0||n==0)return 0;
	else
	{
		if(X[m]==Y[n])return LCSLength(X,Y,m-1,n-1)+1;
		else
		{
			int max1=LCSLength(X,Y,m-1,n);
			int max2=LCSLength(X,Y,m,n-1);
			return max1>max2?max1:max2;
		}
	}
}



void LCSLength(string& X，string& Y，vector<vector<int>>& c,vector<vector<int>& s)
{
	int n=X.size()-1;
	int m=Y.size()-1;
	for(int i=0;i<=n;++i) c[i][0]=0;
	for(int j=0;j<=m;++j) c[0][j]=0;
	for(int i=0;i<=n;++i)
	{
		for(int j=0;j<=m;++j)
		{
			if(X[i]==Y[j])
			{
				c[i][j]=c[i-1][j-1]+1;
				s[i][j]=1;
			}
			else if(c[i-1][j]>c[i][j-1])
			{
				c[i][j]=c[i-1][j];
				s[i][j]=2;
			}
			else
			{
				c[i][j]=c[i][j-1];
				s[i][j]=3
			}
		}
	}
}

动态规划（生兔子问题）

有一对兔子，从出生后3个月起每月都生一对兔子，兔子涨到第三个月后每月有声一对兔子，假如兔子不死，问第24个月的兔子总数为多少。

int fun(int n)
{
	if (n <= 2)return 1;
	int* ar = new int[n + 1];
	ar[1] = 1;
	ar[2] = 1;
	for (int i = 3;i <= n;++i)
	{
		ar[i] = ar[i - 1] + ar[i - 2];
	}
	int total = ar[n];
	delete[]ar;
	return total;
}


//递归
int fac(int n,int a,int b)
{
	if(n==1||n==2)return a;
	return fac(n-1,a+b,a);
}
int fac(int n)
{
	int a=1,b=1;
	return fac(n,a,b);
}

dp[i][j]
i==1   i>1
j==1   j>1
dp[i][j]=dp[i-1][j]+dp[i][j-1]