c++动态规划经典算例_算法的算例怎么写

基本思想

         动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

重要分析问题方法

        动态规划算法跟数组有着密切的关系，因此推荐大家在分析动态规划的算法时画一张表格（建议使用excel）分析解决问题往往能够事半功倍。

动态规划算法实例

1、台阶问题

 问题描述：有10级台阶，一个人每次上一级或者两级，问有多少种走完10级台阶的方法。

结合表格分析问题，每个子问题都只跟台阶这个变量相关，可以画出一个一维表格进行分析。

分析边界条件：对于每个台阶每次上一级或者两级，当台阶数为1时走法为1（即走一级即毕）为2时走法为2（走两次一级和走一次二级）。

分析递归关系：对于任一台阶都可以分为通过两级或者一阶到达。

         $arry[n]=arry[n-1]+arry[n-2]$

终于，在有了上述两个条件之后，问题轻易得到了求解。（结合表格分析的手段到这里还没有完全发挥出它该有的优势，大家拭目以待）

台阶问题基于c++的代码实现：

// ConsoleApplication2.cpp : 定义控制台应用程序的入口点。
//
//台阶问题：有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
#include "stdafx.h"
#include <iostream>
using namespace std;
int getResultByDP(int n)//自底向上的问题解法
{
	if (n<1)
	{
		return 0;
	}
	if (n==1)
	{
		return 1;
	}
	if (n==2)
	{
		return 2;
	}
	int a = 1;//从两个递归基开始
	int b = 2;
	int temp = 0;
	for (int i = 3; i < n + 1; i++)
	{
		temp = a + b;
		a = b;
		b = temp;
	}
	return temp;
}
int _tmain(int argc, _TCHAR* argv[])
{
	cout << getResultByDP(10);
	system("pause");
	return 0;
}
 

2、从矩阵左上角走到右下角最短路径问题

问题描述：给定一个矩阵m，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和，如果给定的m如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12.

1 3 5 9

8 1 3 4

5 0 6 1

8 8 4 0

 

边界条件分析：由问题知道对于任一矩阵中的元素而言，上次位置或者是在该元素的坐标或者上边。那么当一些元素没有左边或者上边时应该怎么做呢？不妨就说的更为具体一些吧，如上图的表格所示当x(表示行下标)等于1，和y（表示列下标）等于1时正好是对应没有上边元素和没有左边元素的情况。对于只有左边元素的值array[x][y]=array[x][y-1]+m[x][y],对于只有上边元素:array[x][y]=array[x-1][y]+m[x][y]（array为下面统计问题结果的二维数组，m为包含输入矩阵信息的二维数组）。

递归公式：对于平凡的子问题而言 （推导递归公式时刻意的考察array[x][y]和array[x-1][y]与array[x][y-1]的实际关系）

对于此问题而言：arry[x][y]=min(array[x-1][y],array[x][y-1])+m[x][y]

以下是该问题基于c++的代码实现：

//给定一个矩阵m，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和，如果给定的m如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12.
#include "stdafx.h"
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int const x_length=5, y_length=5;
int m[x_length][y_length] = {
	0, 0, 0, 0, 0,
	0, 1, 3, 5, 9,
	0, 8, 1, 3, 5,
	0, 5, 0, 6, 1,
	0, 8, 8, 4, 0
};
int minDis() //m二级指针（可以是一个二维数组）
{
	int dp[4 + 1][4 + 1];
	//---------初始化边界条件-----------------
	for (size_t i = 0; i < x_length; i++)
	{
		dp[i][0] = 0;
	}
	for (size_t j = 0; j < y_length; j++)
	{
		dp[0][j] = 0;
	}
	//-------------------------------------------
	for (size_t i = 1; i < x_length; i++)
	{
		for (size_t j= 1; j < y_length; j++)
		{
			if (i == 1)
			{
				dp[i][j] = dp[i][j - 1] + m[i][j];
			}
			else if (j == 1)
			{
				dp[i][j] = dp[i - 1][j] + m[i][j];
			}
			else
			{
				int temp1 = dp[i - 1][j] + m[i][j];
				int temp2 = dp[i][j - 1] + m[i][j];
				dp[i][j] = min(temp1, temp2);
			}			
		}
	}
	return dp[x_length - 1][y_length - 1];
}
int _tmain(int argc, _TCHAR* argv[])
{
	cout << "最右下角的最短路径为：" << minDis();
	system("pause");
	return 0;
}

3、最大子数组问题

问题描述：给定数组arr，返回arr的最长递增子序列的长度，比如arr=[2,1,5,3,6,4,8,9,7]，最长递增子序列为[1,3,4,8,9]返回其长度为5，由于该问题中总要把当前元素和在他之前的进行分析，我们也是借助表格来直观的分析该问题。

边界条件：显然对于第一个数而言有dp[0]=1(dp表示存放结果的数组)

递归公式：首先生成dp[n]的数组，dp[i]表示以必须arr[i]这个数结束的情况下产生的最大递增子序列的长度。对于第一个数来说，很明显dp[0]为1，当我们计算dp[i]的时候，我们去考察i位置之前的所有位置，找到i位置之前的最大的dp值，记为dp[j](0=<j<i),dp[j]代表以arr[j]结尾的最长递增序列，而dp[j]又是之前计算过的最大的那个值，我们在来判断arr[i]是否大于arr[j],如果大于dp[i]=dp[j]+1.计算完dp之后，我们找出dp中的最大值，即为这个串的最长递增序列。

该问题基于c++的代码实现：

//给定数组arr，返回arr的最长递增子序列的长度，比如arr=[2,1,5,3,6,4,8,9,7]，最长递增子序列为[1,3,4,8,9]返回其长度为5.
#include "stdafx.h"
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int dp[5] = {};
int _tmain(int argc, _TCHAR* argv[])
{
	int arr[5] = { 2, 4, 5, 3, 1 };
	dp[0] = 1;
	const int oo = 0;
	for (int i = 1; i<5; i++){
		int _max = oo;
		for (int j = 0; j<i; j++)
			if (dp[j]>_max && arr[i]>arr[j])
				_max = dp[j];
		dp[i] = _max + 1;
	}
	int maxlist = 0;
	for (int i = 0; i < 5; i++)
		if (dp[i] > maxlist)
			maxlist = dp[i];
	cout << maxlist << endl;
	system("pause");
	return 0;
}

4、最长公共子序列

问题描述：给定两个字符串str1和str2，返回两个字符串的最长公共子序列，例如：str1="1A2C3D4B56",str2="B1D23CA45B6A","123456"和"12C4B6"都是最长公共子序列，返回哪一个都行。

问题分析：首先生成dp[n]的数组，dp[i]表示以必须arr[i]这个数结束的情况下产生的最大递增子序列的长度。对于第一个数来说，很明显dp[0]为1，当我们计算dp[i]的时候，我们去考察i位置之前的所有位置，找到i位置之前的最大的dp值，记为dp[j](0=<j<i),dp[j]代表以arr[j]结尾的最长递增序列，而dp[j]又是之前计算过的最大的那个值，我们在来判断arr[i]是否大于arr[j],如果大于dp[i]=dp[j]+1.计算完dp之后，我们找出dp中的最大值，即为这个串的最长递增序列。

该问题基于c++代码实现：

//输入为两个长度不为零的字符串，输出这两个字符串的最大公共子序列
#include "stdafx.h"
#include <string>
#include <iostream>
#ifndef MAX
#define MAX(X,Y) ((X>=Y)? X:Y)
#endif
using namespace std;
int **Lcs_length(string X, string Y, int **B)
{
	int x_len = X.length();
	int y_len = Y.length();
	int **C = new int *[x_len + 1];
	for (int i = 0; i <= x_len; i++)
	{
		C[i] = new int[y_len + 1];        //定义一个存放最优解的值的表；
	}
	for (int i = 0; i <= x_len; i++)
	{
		C[i][0] = 0;
		B[i][0] = -2;                     //-2表示没有方向
	}
	for (int j = 0; j <= y_len; j++)
	{
		C[0][j] = 0;
		B[0][j] = -2;
	}
	for (int i = 1; i <= x_len; i++)
	{
		for (int j = 1; j <= y_len; j++)
		{
 
			if (X[i - 1] == Y[j - 1])
			{
				C[i][j] = C[i - 1][j - 1] + 1;
 
				B[i][j] = 0;             //0表示斜向左上
			}
			else
			{
				if (C[i - 1][j] >= C[i][j - 1])
				{
					C[i][j] = C[i - 1][j];
					B[i][j] = -1;       //-1表示竖直向上；
				}
				else
				{
					C[i][j] = C[i][j - 1];
					B[i][j] = 1;        //1表示横向左
				}
			}
 
		}
	}
	return C;
}
 
void OutPutLCS(int **B, string X, int str1_len, int str2_len)
{
	if (str1_len == 0 || str2_len == 0)
	{
		return;
	}
	if (B[str1_len][str2_len] == 0)   //箭头斜向左上
	{
		OutPutLCS(B, X, str1_len - 1, str2_len - 1);
		cout << X[str1_len - 1] << endl;
	}
	else if (B[str1_len][str2_len] == -1)
	{
		OutPutLCS(B, X, str1_len - 1, str2_len);
	}
	else
	{
		OutPutLCS(B, X, str1_len, str2_len - 1);
	}
}
 
int _tmain(int argc, _TCHAR* argv[])
{
	string X = "ABCBDAB";
	string Y = "BDCABA";
 
	int x_len = X.length();
	int y_len = Y.length();
 
	int **C;//定义一个二维数组
 
	int **B = new int *[x_len + 1];
	for (int i = 0; i <= x_len; i++)
	{
		B[i] = new int[y_len + 1];
	}
	C = Lcs_length(X, Y, B);
	for (int i = 0; i <= x_len; i++)
	{
		for (int j = 0; j <= y_len; j++)
		{
			cout << C[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
	for (int i = 0; i <= x_len; i++)
	{
		for (int j = 0; j <= y_len; j++)
		{
			cout << B[i][j] << " ";
		}
		cout << endl;
	}
	OutPutLCS(B, X, x_len, y_len);//构造最优解
	system("pause");
	return 0;
}