数字三角形（三种）

86 阅读 0 评论 57 点赞

我是靠谱客的博主想人陪蜡烛，最近开发中收集的这篇文章主要介绍数字三角形（三种），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题：、

代码：

#include <iostream>
using namespace std;
int a[101][101];
int n;
//int sum1;
//int sum2;如果是在外面定义的就会出错得出结果是25，在里面定义不会出错，为啥？ 
int  c(int i,int j)
{
	
	if(i==n)
	return a[i][j];//最后一行，递归结束 
	int sum1=c(i+1,j+1);//随机生成
	int sum2=c(i+1,j);
	
    if(sum1>sum2)
	return sum1+a[i][j]; 
    else 
    return sum2+a[i][j];

}

int main() {
	cin>>n;
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
        cin>>a[i][j];
    }
	cout<<c(1,1)<<endl;
	return 0;
}

总结：

全局变量和局部变量的区别，在递归体中，如果要返回递归的结果中有一个变量，这个变量不要设置为全局，因为递归需要的是上一步的结果，这个结果需要计算得出，递归函数中新定义的变量需要进一步求出值，而全局变量的值为上一个储存的值，这样会产生错误

优化：

#include <iostream>
#include<memory.h> 
#include<string>
int a[101][101];
int aset[101][101];//保留修改后的结果 
int n;
using namespace std;
int fun(int i,int j)
{
	int sum1,sum2;
	if(i==n)
	{
	return a[i][j];	
	}
	else
	{
		if(aset[i+1][j]==-1)
		{
		aset[i+1][j]=fun(i+1,j);//都是下一行的
		}
 
    if(aset[i+1][j+1]==-1)
    {
    	aset[i+1][j+1]=fun(i+1,j+1);//都是下一行的
    }
    //int sum2=fun(i+1,j+1);	
	if(aset[i+1][j]>aset[i+1][j+1])
	return fun(i+1,j)+a[i][j];
	else
	return fun(i+1,j+1)+a[i][j];
	}
    		
}
int main() {
	cin>>n;
	int i,j;
	memset(aset,-1,sizeof(aset));//全部设置成0表示多有的函数都没有计算过 
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
		{
			cin>>a[i][j];
		}
	}
	int maxsum=fun(1,1);
	cout<<maxsum;
	return 0;
}

总结：

照样运用了递归，但是这里面的递归结果会保留数组aset[]里面，下次需要的话可以直接取出，不必再递归出结果，节约时间空间。

将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，就叫做“动态规划”。动态规划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的。以上题为例，最佳路径上面的每个数字到底部的那一段路径，都是从该数字出发到达到底部的最佳路径。

//调用子问题求解

#include<iostream>
#include<memory.h>
using namespace std;
int a[101][101];
int aset[101][101];
int n;
int main()
{
	cin>>n;
	memset(aset,-1,sizeof(aset));//置初值 
	int i,j;
	for(i=1;i<=n;i++)//输入 
	{
		for(j=1;j<=i;j++)
		{
			cin>>a[i][j];
		}
	}
	for(j=1;j<=n;j++){
		aset[n][j]=a[n][j];//最后一行的所有值都存在数组里面 
	}
	for(i=n;i>1;i--)//从最后一行开始 
	{
		for(j=1;j<i;j++)//从第一列开始 
		{
			if(aset[i][j]>aset[i][j+1])//找出最大的一列 
			aset[i-1][j]=aset[i][j]+a[i-1][j];
			else
			aset[i-1][j]=aset[i][j+1]+a[i-1][j];
		} 
	} 
	cout<<aset[1][1];//从下至上走到顶 
	return 0;
}

动态规划解题的一般思路
许多求最优解的问题可以用动态规划来解决。用动态规划解题，首先要把原问题分解为
若干个子问题，这一点和前面的递归方法类似。区别在于，单纯的递归往往会导致子问题被
重复计算，而用动态规划的方法，子问题的解一旦求出就会被保存，所以每个子问题只需求
解一次。

子问题经常和原问题形式相似，有时甚至完全一样，只不过规模从原来的
n变成了 n-1，或从原来的 n×m变成了 n×(m-1) ……等等。找到子问题，就意味着找到了将整个问题逐
渐分解的办法，因为子问题可以用相同的思路分解成子子问题，一直分解下去，直到最底层
规模最小的的子问题可以一目了然地看出解（象上面数字三角形的递推公式中，
r=N时，解就是一目了然的）。每一层子问题的解决，会导致上一层子问题的解决，逐层向上，就会导
致最终整个问题的解决。如果从最底层的子问题开始，自底向上地推导出一个个子问题的解，
那么编程的时候就不需要写递归函数。

在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个“状态”。一个“状态”对应于一个或多个子问题，所谓某个“状态”下的“值”，就是这个“状态”所对应的子问题的解。

具体到数字三角形的例子，子问题就是“从位于 (r，j)数字开始，到底边路径的最大和”。这个子问题和两个变量 r和 j相关，那么一个“状态”，就是
r, j的一组取值，即每个数字的位置就是一个“状态”。该“状态”所对应的“值”，就是从该位置的数字开始，到底边的最佳路径上的数字之和。

定义出什么是“状态”，以及在该“状态”下的“值”后，就要找出不同的状态之间如何迁移―――即如何从一个或多个“值”已知的“状态”，求出另一个“状态”的“值”。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。

如下的递推式就说明了状态转移的方式：

上面的递推式表明了如果知道了状态（ r＋1，j）和状态（r+1，j+1）对应的值，该如何求出状态(r，j)对应的值，即两个子问题的解决，如何导致一个更高层的子问题的解决。

所有“状态”的集合，构成问题的“状态空间”。“状态空间”的大小，与用动态规划解决问题的时间复杂度直接相关。在数字三角形的例子里，一共有
N×(N+1)/2个数字，所以
这个问题的状态空间里一共就有 N×(N+1)/2个状态。在该问题里每个“状态”只需要经过一次，且在每个状态上作计算所花的时间都是和 N无关的常数。

用动态规划解题，经常碰到的情况是，K个整型变量能构成一个状态（如数字三角形中
的行号和列号这两个变量构成“状态”）。如果这 K个整型变量的取值范围分别是
N1, N2, …… Nk，那么，我们就可以用一个
K维的数组
array[N1] [N2]……[Nk]来存储各个状态的“值”。

这个“值”未必就是一个整数或浮点数，可能是需要一个结构才能表示的，那么 array就可以是一个结构数组。一个“状态”下的“值”通常会是一个或多个子问题的解。
用动态规划解题，

如何寻找“子问题”，定义“状态”，“状态转移方程”是什么样的，并没有一定之规，需要具体问题具体分析，题目做多了就会有感觉。甚至，对于同一个问题，
分解成子问题的办法可能不止一种，因而“状态”也可以有不同的定义方法。不同的“状态”
定义方法可能会导致时间、空间效率上的区别