算法 动态规划

动态规划

• 最长公共子序列
• • 动态规划实现
  • 非递归实现
• 兔子出生
• 机器人移动

动态规划算法与分治策略类似，其基本思想也是将待求问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解；与分治法不同的是，适合于用动态规划发求解的问题，经分解得到的子问题往往不是相互独立的，若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要消耗指数时间；然而，不同子问题的数目常常只有多项式量级；在用分治法求解时，有些子问题被重复计算了许多次；如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法；为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案；不管孩子问题以后是否被用到，只要它被计算过，就将其结果填入表中；这就是动态规划法的基本思想；具体的动态规划算法是多种多样的，但他们具有相同的填表格式

• 动态规划算法适用于解最优化问题，通常可以按一下步骤设计动态规划算法：

1. 找出最优解的性质，并刻画其结构特征
2. 递归地定义最优值
3. 以自底向上的方式计算出最优值
4. 根据计算最优值时得到的信息，构造最优解

最长公共子序列

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;
		}
	}
}

int main()
{
	char X[] = { "#ABCBDAB" };

	char Y[] = { "#BDCABA" };

	int xm = strlen(X) - 1, yn = strlen(Y) - 1;

	int maxlen = LCSLength(X, Y, xm, yn);
	cout << maxlen << endl;
}

在这里与分治策略所不同的就是，出现了重复求解的过程，其时间复杂度随着指数型增长

动态规划实现

使用动态规划思想，加入一个二维数组，进行记录求结果的过程，当再次到达此处则不再做重复计算

第二个二位数组的引入是为了记录最长公共子序列的走向，通过计数来推导出最长公共子序列

template<class T>
void Print_Vec(vector<vector<T>>& c)
{
	int m = c.size();
	for (int i = 0; i < m; i++)
	{
		int n = c[i].size();
		for (int j = 0;j < n; j++)
		{
			cout << setw(3) << c[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
int LCSLength(const char* X, const char* Y, int m, int n, vector<vector<int>> &c, vector<vector<int>> &s)
{
	if (m == 0 || n == 0) return 0;
	else if (c[m][n] != 0) return c[m][n];
	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 - 1, n, c,s);
			int max2 = LCSLength(X, Y, m, n - 1, 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<vector<int>>& 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
	{
		LCS(X, s, i, j - 1);
	}
}


int main()
{
	char X[] = { "#ABCBDAB" };

	char Y[] = { "#BDCABA" };

	int xm = strlen(X) - 1, yn = strlen(Y) - 1;

	vector<vector<int>> c; //动态开辟二维数组
	vector<vector<int>> s;
	c.resize(xm + 1);
	s.resize(xm + 1);
	for (int i = 0; i < xm + 1; i++)
	{
		c[i].resize(yn + 1, 0);
		s[i].resize(yn + 1, 0);
	}

	int maxlen = LCSLength(X, Y, xm, yn, c, s);
	Print_Vec(c);
	Print_Vec(s);
	cout << maxlen << endl;

	LCS(X, s, xm, yn);
	return 0;
}

非递归实现

template<class T>
void Print_Vec(vector<vector<T>>& c)
{
	int m = c.size();
	for (int i = 0; i < m; i++)
	{
		int n = c[i].size();
		for (int j = 0; j < n; j++)
		{
			cout << setw(3) << c[i][j];
		}
		cout << endl;
	}
	cout << endl;
}

void LCS(string& X, vector<vector<int>>& 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                   //行
	{
		LCS(X, s, i, j - 1);
	}
}
int 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 = 1; i <= n; i++)
	{
		for (int j = 1; 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][j - 1] > c[i - 1][j])
			{
				c[i][j] = c[i][j - 1];
				s[i][j] = 3;
			}
			else
			{
				c[i][j] = c[i - 1][j];
				s[i][j] = 2;
			}
		}
	}
	return c[n][m];
}


int main()
{
	string X = { "#ABCBDAB" };

	string Y = { "#BDCABA" };

	int xm = X.size() - 1, yn = Y.size() - 1;

	vector<vector<int>> c; //动态开辟二维数组
	vector<vector<int>> s;
	c.resize(xm + 1);
	s.resize(xm + 1);
	for (int i = 0; i < xm + 1; i++)
	{
		c[i].resize(yn + 1, 0);
		s[i].resize(yn + 1, 0);
	}


	cout << LCSLength(X, Y, c, s) << endl;

	Print_Vec(c);
	Print_Vec(s);
	LCS(X, s, xm, yn);
	
	return 0;
}

兔子出生

有一对兔子，从出生后第三个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问第24个月的兔子总数为多少？

int fun(int n)
{
	if (n <= 2) return 1;
	int* ar = new int[n + 1]; //0
	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) //递归  时间复杂非常高！！！
{
	if (n == 1 || n == 2) return 1;
	else
		return fac(n - 1) + fac(n - 2);
}
int fac2(int n, int a, int b)
{
	if (n == 1 || n == 2) return a;
	return fac2(n - 1, a + b, a);
}
int fac2(int n)
{
	int a = 1, b = 1;
	return fac2(n, a + b, a); //通过这种方式,减少重复解，减少时间复杂度
}

int main()
{
	int n = 24;
	int total = fun(n);
	return 0;
}

机器人移动

一个机器人位于一个m*n网格的左上角，机器人每次只能向下或者向右移动一步，机器人试图达到网络的右下角

问总共有多少条不同的路径？

动态规划方程式 dp[i][j] = dp[i-1][j] + dp[i][j-1]

int robot(vector<vector<int>>& c,int m ,int n)
{
	for (int i = 0; i < m; i++) c[i][0] = 0;
	for (int j = 0; j < n; j++) c[0][j] = 0;

	if (m == 0 || n == 0) return 0;
	else if (c[m][n] != 0) return c[m][n];
	else if (m == 1 || n == 1)
	{
		c[m][n] = 1;
	}
	else
	{
		c[m][n] = robot(c, m - 1, n) + robot(c, m, n - 1);
	}
	return c[m][n];
}

int main()
{
	int m = 3;
	int n = 3;
	vector<vector<int>> c; //动态开辟二维数组
	c.resize(m + 1);
	for (int i = 0; i < m + 1; i++)
	{
		c[i].resize(n + 1, 0);
	}
	cout << robot(c, m, n) << endl;
}