动态规划，递归动归方式对比分析（C/C++）（典型例题数字三角形/

小白勿喷~~（点亮你的“小红花”）
下面是我对动态规划的一些认识：
动态规划的主要解决的就是一个大问题的最优解，然后这个大问题的最优解可以转化为很多个子问题的最优解，如果无法转化，则不能通过此算法来解决。
我们在将大问题转化为小问题的时候，很容易就会想到用递归的方式解决，但数据过大，重复的递归调用会让我们的时间复杂度变得非常的大。
下面我会通过分析递归调用的方式和动归调用的方式进行解析。
我们就以数字三角形为例子来进行分析。
递归版本：

#include<iostream>
#include<algorithm>
using namespace std;
#define max1 101  
int dp[max1][max1];//定义一个二维数组来保存数字三角形
int n;//表示数字三角形的行数 
int maxsum[max1][max1];//用来保存第i行第j列数字到底边的最大和

int maxs(int i,int j)//求第i行第j列的数字到底边的最大距离的函数
{
	if(i==n)
	  maxsum[i][j]=dp[i][j]; //如果计算的数字在最后一行，就直接返回当前值
	else
	{
		int a=maxs(i+1,j);//当前数字左下的数字,递归调用计算，值为-1就直接从函数中返回值，如果不是就继续往下算，下同 
		int b=maxs(i+1,j+1);//当前数字右下数字，同上 
		maxsum[i][j]=max(a,b)+dp[i][j]; //左下数字和右下数字比较，大的那个加上当前数字 
	 } 
	 return maxsum[i][j];
 } 

int main()
{
	int i,j;
	cin>>n;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=i;j++)
	  {
	  	cin>>dp[i][j];
	  }
	cout<<maxs(1,1)<<endl;
 } 

递归算法的唯一优点就是写法简单，容易理解，但数据一多，重复计算的数字也多，所以容易超时。下面我们来看动态规划计算的版本。
动归方式：

#include<iostream>
#include<algorithm>
using namespace std;
#define max1 101  
int dp[max1][max1];//定义一个二维数组来保存数字三角形
int n;//表示数字三角形的行数 
int maxsum[max1][max1];//用来保存第i行第j列数字到底边的最大和

int maxs(int i,int j)//求第i行第j列的数字到底边的最大距离的函数
{
	if(maxsum[i][j]!=-1)//如果当前值(状态)不为-1，就直接返回当前值，不用再进行重复计算，降低了时间复杂度 
	{
	  return maxsum[i][j]; 
}
	if(i==n)
	  maxsum[i][j]=dp[i][j]; 
	if(maxsum[i][j]==-1)
	{
		int a=maxs(i+1,j);//当前数字左下的数字,递归调用计算，值为-1就直接从函数中返回值，如果不是就继续往下算，下同 
		int b=maxs(i+1,j+1);//当前数字右下数字，同上 
		maxsum[i][j]=max(a,b)+dp[i][j]; //左下数字和右下数字比较，大的那个加上当前数字 
	 } 
	 return maxsum[i][j];
 } 

int main()
{
	int i,j;
	cin>>n;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=i;j++)
	  {
	  	cin>>dp[i][j];
	  	maxsum[i][j]=-1;//为了避免重复计算，我们将第i行第j列的数字到底边距离初始化为-1 
	  }
	cout<<maxs(1,1)<<endl;
 } 

动归方式的计算，就是初始化了每一个数到底边的最大和状态为-1，当算出来了值就不为-1了，下次要调用就直接用其算出来的值，而不用像递归一样，再次重复计算，降低了时间复杂度。
当然这个数字三角形还有一种递推的算法，就是从底层数字往上计算，在计算到每一层的时候，挑选最大的那个数字往上加，直到加到第i行第j列的数字为止，这种算法也可选，我就不写出来了。