第十二届蓝桥杯最短路径（动态规划法）

本文主要是介绍第十二届蓝桥杯最短路径（动态规划法），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include<iostream>
using namespace std;
//辗转相除法（递归）求最大公约数 
int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b,a%b);
 } 
 //求最小公倍数 
 int lcm(int a, int b)
 {
 	return a*b/gcd(a,b);
 }
int main()
{
	//动态规划开辟数组 
	int dp[3000] = {0};
	//求出到每一个点的最短路径，先从第二个点开始 
	for (int i = 2; i <= 2021; i++)
	{
		int minValue = 100000000;//警示****该值要开辟的足够大（至少大于该题答案，题主错在这里） 
		if (i - 21 > 0)//如果大于21,则从i-21开始 
		{
			for (int j = i-21; j < i; j++)
			{
				//到该点的距离为距离小于等于21的任意一点的最短距离（dp[j]) 加上任意一点
				//到该点的距离（即最小公倍数）
				//最短距离就是求出上述 距离的最小值 
				minValue = min(minValue,lcm(j,i) + dp[j]);
			}
		}
		else
		{
			//否则从1开始 
			for (int j = 1; j < i; j++)
			{
				    //同上 
					minValue = min(minValue,lcm(j,i) + dp[j]);
			}
		}
		//该点的最短距离为求得的最小值 
		dp[i] = minValue;
	}
	cout << dp[2021] << endl;
	return 0;
}

这篇关于第十二届蓝桥杯最短路径（动态规划法）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！