详细实例说明+典型案例实现 对动态规划法进行全面分析 | C++

int countval[1000] = { 0 };   //暂存区
int Fib(int n)
{
	int result;
	result = countval[n-1];
	if (result == 0)
	{
		if (n == 1 || n == 2) {
			result = 1;
		}
		else {
			result = Fib(n - 2) + Fib(n - 1);
		}
		countval[n-1] = result;
	}
	return result;
}

#include<iostream>
using namespace std;
int countval[1000] = { 0 };   //暂存区
int Fib(int n)
{
	int result;
	result = countval[n-1];
	if (result == 0)
	{
		if (n == 1 || n == 2) {
			result = 1;
		}
		else {
			result = Fib(n - 2) + Fib(n - 1);
		}
		countval[n-1] = result;
	}
	return result;
}
void text()
{
	int i = 0;
	cout << "请输入要求的第几个斐波那契数：";
	int x; cin >> x;
	cout << "该数为：" << Fib(x) << endl;
	cout << "暂存区中的数据：" << endl;
	while (countval[i] != 0)
	{
		cout << "countval" << "[" << i << "]" << "=" << countval[i] << endl;
		i++;
	}
}
int main()
{
	text();
}

#include<iostream>
using namespace std;
#define maxnum 20   //自定义图的最大的顶点数
#define maxvalue 65535
#define yes 0    //已选用顶点
#define no -1	//非邻接顶点
typedef struct {
	char vertex[maxnum];    //顶点信息
	int g_type;      //图的类型
	int vertex_num;		//顶点的数量
	int edge_num;		//边的数量
	int edge_weight[maxnum][maxnum];	//边的权
}graphmatrix;   
void creategraph(graphmatrix& gm)
{
	int weight;  //权重
	char start_vertex, end_vertex;   //起始两顶点
	int i,j,k;
	cout << "###请输入图中各顶点信息###" << endl;
	for (i = 0; i < gm.vertex_num; i++)
	{
		cout << "第" << i + 1 << "个城市:";
		cin >> gm.vertex[i];
	}
	cout << "###请输入图中构成各边的左右顶点以及该边的权值###" << endl;
	for (k = 0; k < gm.edge_num; k++)
	{
		cout << "第" << k + 1 << "条边:";
		cin >> start_vertex >> end_vertex >> weight;
		for (i = 0; start_vertex != gm.vertex[i]; i++)     //查找始点
		{
			for (j = 0; end_vertex != gm.vertex[j]; j++)   //查找终点
			{
				gm.edge_weight[i][j] = weight;                 //找到后将权值保存
			}
		}
		if (gm.g_type == 0)
		{
			gm.edge_weight[j][i] = weight;
		}
	}
}
void clear_graph(graphmatrix& gm)
{
	for (int i = 0; i < gm.vertex_num; i++)
		for (int j = 0; j < gm.vertex_num; j++)
			gm.edge_weight[i][j] = maxvalue;
}
void min_graph(graphmatrix &gm)
{
	int min, sum=0;
	int weight[maxnum];
	char vertex_[maxnum];
	int k;
 
	for (int i = 1;i< gm.vertex_num; i++)
	{
		weight[i] = gm.edge_weight[0][i];       //保存邻接矩阵中的一行数据
		if (weight[i] == maxvalue)
			vertex_[i] = no;
		else
			vertex_[i] = gm.vertex[0];
	}
	vertex_[0] = yes;
	weight[0] = maxvalue;
	for (int i = 1; i < gm.vertex_num; i++)
	{
		min = weight[0];
		k = i;
		for (int j = 1; j < gm.vertex_num; j++)
		{
			if (weight[j] < min && vertex_[j]>0)   //寻找具有更小权值的边
			{
				min = weight[j];
				k = j;
			}
		}
		sum += min;    //将权值进行累加
		vertex_[k] = yes; 
		weight[k] = maxvalue;
		for (int j = 0; j < gm.vertex_num; j++)
		{
			if (gm.edge_weight[k][j] < weight[j] && vertex_ != 0)
			{
				weight[j] = gm.edge_weight[k][j];
				vertex_[j] = gm.vertex[k];
			}
		}
	}
	cout << endl;
	cout << "最短路径的总长度为：" << sum << endl;
}
void text()
{
	graphmatrix gm;
 
	cout << "###创建图###" << endl;
	cout << "输入图的类型（0:无向图 1:有向图）:";
	cin >> gm.g_type;
	cout << "输入图中城市的数量:";
	cin >> gm.vertex_num;
	cout << "输入图中城市间路径的数量:";
	cin >> gm.edge_num;
 
	clear_graph(gm);
	creategraph(gm);   //构建图
	min_graph(gm);   //最小生成树算法 ,动态规划的使用块
}
int main()
{
	text();
}