动态规划经典问题：全面探讨数字三角形(数塔问题)(C/C++)

题目简述(题目:2127' https://www.dotcpp.com/oj/problem2127.html  '):

        数字三角形如下: 

                 7

                3 8

               8 1 0

              2 7 4 4

             4 5 2 6 5

        在上面的数字三角形中寻找一条从顶部到底部的路径，使得路径上所经过的数字之和

最大。路径上的每一步都只能往左下或者右下走。

三角形的行数大于1小于等于100，数字为0-99.

我们先考虑怎么存:

        很容易就想到用二维数组a[N][N]来存储，样例输入：

         5
        13
        11   8
        12   7   26
         6   14  15   8
        12   7   13  24 11

//输入功能
void input(int a[N][N],int n)
{
	int i,j;
	for(i=1;ia[i][j];
}

思路探讨:

        从下往上走,将倒数第二行相邻的最后一行元素中的最大值与自身相加,

并替换当前元素,循环此操作,一直到最顶端为止,输出最顶端元素的值就是所得的最大值

我们从下往上推出来的动态转移方程公式：max = a[i+1][j]>=a[i+1][j+1] ? a[i+1][j] : a[i+1][j+1];

我们从小往上递推一下

图解思想:

经上面的图解探讨，可以看出从下往上选最大并更新上一层，以此类推，最后一张图就是只剩下最后所要结果：86

这样可以用递推思想去设计更直观些

我们要用递归写的话，直接从上往下推，更适合递推算法的一层一层深入的模式，一直深入到最底层在按上面图解方式一层一层回溯上来！

递归：

我们用MaxSum(r, j)表示从a(r,j)到底边的各条路径中，最佳路径的数字之和。
因此，此题的最终问题就变成了求 MaxSum(1,1)
当我们看到这个题目的时候，首先想到的就是可以用简单的递归来解题：
a(r, j)出发，下一步只能走a(r+1,j)或者a(r+1, j+1)。故对于N行的三角形，我们可以写出如下的递归式：

if ( r == N)                
    MaxSum(r,j) = a(r,j)  
else      
    MaxSum( r, j) = Max{ MaxSum(r＋1,j), MaxSum(r+1,j+1) } + a(r,j)

上面一番讨论借用上面简单的递归思想直接实现：

#include   
#include  
#define MAX 500
using namespace std; 
int a[MAX][MAX];  
int n;  
int MaxSum(int i, int j){    
    if(i==n)  
        return a[i][j];    
    int x = MaxSum(i+1,j);    
    int y = MaxSum(i+1,j+1);    
    return max(x,y)+a[i][j];  
}
int main(){    
    int i,j;    
    cin >> n;    
    for(i=1;i a[i][j];    
    cout << MaxSum(1,1) << endl;  
}

上面的代码很暴力，当中有大量重复计算O(2^n) 

因此我们用DP来优化，使之成为记忆递归型的动态规划程序：

#include   
#include  
using namespace std;

#define MAX 500

int a[MAX][MAX];    
int n;  
int maxSum[MAX][MAX];

int MaxSum(int i, int j){      
    if( maxSum[i][j] != -1 )         
        return maxSum[i][j];      
    if(i==n)   
        maxSum[i][j] = a[i][j];     
    else{    
        int x = MaxSum(i+1,j);       
        int y = MaxSum(i+1,j+1);       
        maxSum[i][j] = max(x,y)+ a[i][j];     
    }     
    return maxSum[i][j]; 
} 
int main(){    
    int i,j;    
    cin >> n;    
    for(i=1;i a[i][j];       
            maxSum[i][j] = -1;   
        }    
    cout << MaxSum(1,1) << endl; 
}

从下往上推，往下方便我们优化空间

递推：

虽然在短时间内就AC了。但是，我们并不能满足于这样的代码，因为递归总是需要使用大量堆栈上的空间，很容易造成栈溢出，我们现在就要考虑如何把递归转换为递推，让我们一步一步来完成这个过程。

根据动态转移方程，我们用一个C函数来概括出递推的过程：

//循环倒叙往上加
void cancle(int a[N][N],int n)
{
	int i,j,max=0;
	for(i=n-1;i>=1;i--)
		for(j=1;j=a[i+1][j+1]?a[i+1][j]:a[i+1][j+1];
			//更新当前元素的值
			a[i][j]=a[i][j]+max;	 //让其自己和自己下方相邻元素的最大值相加
		}
	printf("%d",a[0][0]);                    //C++:cout<<a[0][0];
}

我们添加一项来探讨：

当我不仅仅要最大值，而且还要打印出从下往上累加的路线，那我们该怎么办？？

很简单，用多维数组来存储该过程：a[3][N][N]

C代码详解：

#includeint main01()
{
	int n,a[3][500][500],i,j;
	//printf("请输入数塔的层数:");
	scanf("%d",&n);
	//printf("请输入数塔:\n");
	getchar();
	for(i=1;i<=n;i++)
		for(j=1;j=1;i--)
		for(j=1;ja[2][i+1][j+1])
			{
				a[2][i][j]=a[2][i][j]+a[2][i+1][j];
				a[0][i][j]=0; 
			}
			else
			{
				a[2][i][j]=a[2][i][j]+a[2][i+1][j+1];
				a[0][i][j]=1;
			}
			printf("%d\n",a[2][1][1]);
			for(i=1,j=1;i<n;i++)
			{
				printf("%d->",a[1][i][j]);
				j=j+a[0][i][j];
			}
			printf("%d\n",a[1][n][j]);
	return 0;
}

运行结果图：

注意：

虽然我们通过上面的步骤一步一步的走过来，但是，当我们再深入探讨的时候，就有发现问题了，如果我们存入的数塔非常大，那么我们开辟的内存空间也会非常大，这样就会导致大量的空间资源浪费，所以我们可以借助滚动数组来优化算法（我博客中"背包问题"也提到过:' https://blog.dotcpp.com/a/73345  '，可以通过多种不同类型题来提高该方面的理解）

在改变之前，我们需要先改进思路，用两个二维数组来实现：

#include#includeusing namespace std;
/* 
int main()
{
	int i,j,D[500][500],maxsum[500][500],n;
	for(i = 0;i < n;i ++)
		for(j = 0;j < n;j ++)
			cin>>a[i][j];
	//把a数组最后一行放入b数组 
	for(i = 0;i < n;i ++)
		maxsum[i][j] = a[i][j];
	//从下往上递推
	for(i = n - 2;i >= 0;i --)
		for(j = 0;j <= i;j ++)
			maxsum[i][j] = max(maxsum[i+1][j],maxsum[i+1][j+1]) + D[i][j];
	//打印顶端
	cout<<maxsum[0][0]<<endl;
	return 0;
}
*/

回到思想探讨上：

        我们可以在创建一个一位数组，用一位数组从下往上在保存数据的二维数组上执行，每执行一行数组往上挪动，滚动到最后直接打印一维数组第一个元素即可！

C代码演示：

#include#includeusing namespace std;

/*空间优化
	没必要用二维数组存储每一个相对大的元素(maxa[][])，只要从底层一行行向上递推，
那么只要一维数组(maxa[])即可，即只要存储一行maxa[]值就可以。 

空间再优化
	不要maxsum一维数组也不要了，一直用D的第n行，达到空间优化。
*/ 
int main()
{
	//用一个maxsum指针来代替数组功能 
	int i,j,a[500][500],*maxsum,n;
	cin>>n;
	for(i = 1;i a[i][j];
	//让maxsum指向第n行 
	maxsum = a[n];
	//从下往上递推
	for(i = n - 1;i >= 1;i --)
		for(j = 1;j <= i;j ++)
			maxsum[j] = max(maxsum[j],maxsum[j+1]) + a[i][j];
	//打印顶端
	cout<<maxsum[1];
	return 0;
}

数塔问题的整个探讨过程是很有价值的，尤其是对于刚接触动态规划问题的人，需要多深究这些经典问题！

在精不在多！