动态规划原理

引言：

????????首先在这新的一年，祝大家能在自己的领域大展宏图！！！！

? ? ? ? 下面问大家一个问题：

? ? ? ? 这是一个三角型数字阵列

????????从最顶端开始只能向下加左边或右边的数，问怎莫选择路径会更是得到的结果最大?，输出最大值。

????????最简单的方法就是求出所有的可能结果然后输出最大值，这种方式固然简单，放再这个题上也可以解决问题。

????????但是如果这个三角形有100000层该如何计算呢，暴力破解几乎不可能，这就需要有一种算法进行时间是复杂度优化，这个算法就是动态规划！！！

原理分析：

? ? ? ? 暴力破解之所以耗费时间是因为进行了大量的重复计算，如果能让每次计算的结果被存储下来在需要相同计算的时候就可以直接调用结果，这样就可以节省大量的时间从而降低时间复杂度，换句话来说就是“用空间换时间”。

? ? ? ? 换一个方向从下向上开始计算：

将两个较小的值加到上一次层的数上然后将较大的一个值替换掉原来的值?计算后的结果就像这样：

然后一次类推一直加到最顶端：

由于每一层都是最大的数，所以这时最顶端的数就是我们要求的最大值；

这样计算的话就会省去大量计算重复路径的时间。

代码实现：

#include<iostream>
using namespace std;

#define MAX 100000

int main()
{
	for (int i = 1; i <= 100000; i++)
		for (int j = 1; j <= i; j++)
			cin >> nums[i][j];
	for (int i = n - 1; i >=1 ; i--)
		for (int j = 1; j <= i; j++)
			nums[i][j] += max(nums[i + 1][j],nums[i + 1][j + 1] ); //存储最大值

	cout << nums[1][1] << endl;
	return 0;
}

结语：

? ? ? ? 动态规划的原理就像是做定期的总结，做好总结会提升效率减少进步的时间复杂度！！！

? ? ? ? 这篇文章到此结束，希望会对大家理解动态规划思想原理起到帮助，我们下一篇文章再见！