动态规划，最长公共子序列，机器人路径，打家劫舍

• • 定义
  • 最长公共子序列
  • 机器人路径
  • 打家劫舍

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;

template
void Printf_Vec(vector>& c)
{
	for (int i = 0;i < c.size();++i)
	{
		for (int j = 0;j < c[i].size();++j)
		{
			cout <>&c)
{
	if (m == 0 || n == 0) return 0;
	else if (c[m][n] != 0) return c[m][n];//说明已经计算过了，数组刚开始的值是0；
	else
	{
		if (X[m] == Y[n]) {
		  
			c[m][n]=LCSLength(X, Y, m - 1, n - 1,c) + 1;
		} 
		else
		{
			
			int max1 = LCSLength(X, Y, m, n - 1,c);
			int max2 = LCSLength(X,Y, m - 1, n,c);
			c[m][n] =max1 > max2 ? max1 : max2;
		}
	}
	return c[m][n];
}

int main()
{
	char X[] = { "#ABCBDAB" };
	//            01234567
	char Y[] = { "#BDCABA" };
	//            0123456#避免数组里面的0下标
	int xm = strlen(X) - 1;
	int yn = strlen(Y) - 1;
	vector>c;
	c.resize(xm + 1);
	for (int i = 0;i < xm + 1;++i)
	{
		c[i].resize(yn + 1);
	}
	int length=LCSLength(X,Y,xm,yn,c);
	Printf_Vec(c);
	cout << length << endl;
	return 0;
}

BDAB
为了记录最长子序，再用一个数组来记录

#include
#include
using namespace std;

template
void Printf_Vec(vector>& c,vector>&s)
{
	for (int i = 0;i < c.size();++i)
	{
		for (int j = 0;j < c[i].size();++j)
		{
			cout <
		for (int j = 0;j < s[i].size();++j)
		{
			cout << s[i][j] <<" ";
		}
		cout << endl;
	}
	cout << endl;
}
int LCSLength(const char*X,const char*Y,int m,int n,vector>&c,vector>&s)
{
	if (m == 0 || n == 0) return 0;
	else if (c[m][n] != 0) return c[m][n];//说明已经计算过了，数组刚开始的值是0；
	else
	{
		if (X[m] == Y[n]) {
		  
			c[m][n]=LCSLength(X, Y, m - 1, n - 1,c,s) + 1;
			s[m][n] = 1;
		} 
		else
		{
			int max1 = LCSLength(X, Y, m, n - 1,c,s);
			int max2 = LCSLength(X,Y, m - 1, n,c,s);
			if (max1 > max2)
			{
				c[m][n]=max1;
				s[m][n] = 2;
			}
			else
			{
			 c[m][n] =max2;
			 s[m][n] = 3;
			}
			
		}
	}
	return c[m][n];
}
void LCS(const char* X, vector>& s, int i, int j)
{
	if (i == 0 || j == 0) return;
	if (s[i][j] == 1)
	{
		LCS(X, s, i - 1,j - 1);
		cout << X[i];
	}
	else if (s[i][j] == 2)
	{
		LCS(X, s, i - 1, j);
	}
	else//s[i][j]==3的时候；
	{
		LCS(X, s, i, j - 1);
	}
}
int main()
{
	char X[] = { "#ABCBDAB" };
	//            01234567
	char Y[] = { "#BDCABA" };
	//            0123456#避免数组里面的0下标
	int xm = strlen(X) - 1;
	int yn = strlen(Y) - 1;
	vector>c,s;
	c.resize(xm + 1);
	s.resize(xm + 1);
	for (int i = 0;i < xm + 1;++i)
	{
		c[i].resize(yn + 1);
		s[i].resize(yn + 1);
	}
	int length=LCSLength(X,Y,xm,yn,c,s);
	Printf_Vec(c,s);
	cout << length << endl;
	LCS(X, s,xm, yn);
	return 0;
}

非递归方式

在这里插入代码片

int fac(vector>&ar,int m,int n) 
{
	if (m == 1 || n == 1) return 1;
	return fac(ar, m - 1, n) + fac(ar, m, n - 1);
}
int main()
{
	int m = 3,n=7;
	vector>ar(m+1, vector(n+1));
	int num = fac(ar,m,n);
	cout << num << endl;
	return 0;
}

int fac(vector&ar,int m) 
{
	if (m == 1) return ar[1];
	else if (m == 2)
	{
		return ar[1] > ar[2] ? ar[1] : ar[2];
	}
	else
	{
	 return fac(ar,m - 1)>fac(ar,m - 2) + ar[m]?fac(ar,m-1):fac(ar,m-2)+ar[m];
	}	
}
int main()
{
	vectorar = {0,1,3,6};//[1,3,6]
	vectorbr = { 0,1,2,3,4 };//[1,2,3,4]
	int num = fac(ar,ar.size()-1);
	int num2= fac(br, br.size() - 1);
	cout << num << endl;
	cout << num2 << endl;
	return 0;
}