动态规划——数字三角形C语言

一：分析

先说一下相关动态规划的一些概念，参考下方博文。

原文链接：https://blog.csdn.net/every__day/article/details/88174082

“一个模型三个特征”理论的讲解
动态规划作为一个非常成熟的算法思想，很多人对此做了非常全面的总结，我把这部分理论总结为“一个模型三个特征”。

首先，“一个模型”指的是动态规划适合解决问题的模型。我把这个模型定义为“多阶段决策最优解模型”。

具体来说，我们一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

“三个特征”，分别是最优子结构、无后效性和重复子问题。这三个概念比较抽象，逐一解释一下。

1、最优子结构

最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面状态推导出来。

2、无后效性

无后效性，有两层含义，第一层含义是，在推导后面阶段状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

3、重复子问题

这个概念，前面一节，已经多次提到。用一句话概括就是： 不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。
 

正常分析很容易想到，自顶向下每次遇到两个分支，每次选取大的分支进行加和，一直到最底层即得到最优解。

但是做动态规划我们一定要注意子问题的解是不是真的可以构成原问题的解。

显而易见在这里回答是否定的。那我们就设法使之满足最优子结构。就是说我们新开辟一个内存空间，去存储对于数塔中每一个数字对于到达最低端的路径最大值。计算完成后答案随之复现。

我们必须选取所有可能的情况中最合适的一个，而不是顺着一个不完全的判定标准走一条路。

这里有两种方式，下面给出每个位置到最低端的最大路径值，这里采取第二种，因为更简单。

输入：

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

①：自顶向下

②：自低向上

顶部值即为所求值。

输出：

二：代码

如下：

#include<stdio.h>
 
int r,max,a[1002][1002],F[1002][1002];//a存储原始三角形信息，F存储最大路径权值和 ，此算法自底向上做 
main()
{
	scanf("%d",&r);
	for(int i=1;i<=r;i++)
		for(int j=1;j<=i;j++)
		{
			scanf("%d",&a[i][j]);
			F[i][j]=a[i][j];
		}
		
	for(int i=r-1;i>0;i--)//二维数组最后一行 
	{
		for(int j=1;j<=i;j++)//二维数组第一列 
		{
			if(F[i+1][j]>F[i+1][j+1])//自底向上依次比较取最大值加和 
			{
				max=F[i+1][j];
			}else{
				max=F[i+1][j+1];
			}
			F[i][j]+=max;
		}
	}
	
	printf("\n\n");
	printf("*********F[i][j]到最低端最大路径和**********\n\n"); 
	//输出F[] []，F[i][j]到最低端最大权值 
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=i;j++)
		{
			if(F[i][j]<10)//为了统一格式，美观
			{
				printf("%d  ",F[i][j]); 
			}else{
				printf("%d ",F[i][j]); 
			}
			
		}
		printf("\n");
	}
	
		
		
	printf("\n\n**************最终结果为：***************\n\n");		
	printf("%d",F[1][1]);//输出最顶端到最低端的最大权值 
}