6.1 动态规划：数字三角形

水深无声 2022-05-12 15:54 222阅读 0赞

![70][]

在上面的数字三角形中寻找一条从顶部到底边的路径，使得 路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。

输入：

5  
7  
3 8  
8 1 0  
2 7 4 4  
4 5 2 6 5

输出：

解析：如果要算第1行第1个数字到底边的最大和，就要先算第2行第1个数字以及第2行第2个数字到底边的最大和；

要算第2行第1个数字到底边的最大和就要第三行第一个和第二个数字到底边的最大和……很明显，这是一个典型的递归问题。

![70 1][]

#include<iostream>
    #define N 100
    using namespace std;
    int a[N][N];
    int n;
    int SumMax(int i, int j)//第i行第j列的数字到底边的最大和 
    {
    	if(i == n)  return a[i][j];
    	else
    		return max(SumMax(i+1,j),SumMax(i+1,j+1))+a[i][j];
    }
    int main()
    {
    	freopen("a.txt","r",stdin);
    	cin >> n;
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= i; ++j)
    		{
    			cin >> a[i][j];
    		}
    	}
    	cout << SumMax(1,1);
    	return 0;
    }

这个代码会超时，因为存在大量的重复计算。比如我们从上往下看，在计算第2行第2个数到底边的最大距离之和时，1这个数字要重复调用2次。第2行第一个数字调用一次，第2行第2个数字又要调用一次。

![70 2][]

【改进】

![70 3][]

改进后的代码：

#include<iostream>
    #define N 100
    using namespace std;
    int a[N][N];
    int maxsum[N][N];
    int n;
    int SumMax(int i, int j)//第i行第j列的数字到底边的最大和 
    {
    	if(maxsum[i][j] != -1)//要一直调用到第n行才会算出结果，然后再出栈算出结果 
    		return maxsum[i][j];
    	if(i == n)  maxsum[i][j] = a[i][j];
    	else
    	{
    		int x = SumMax(i+1,j);
    		int y = SumMax(i+1,j+1);
    		maxsum[i][j] = max(x,y)+a[i][j];
    	}
    	return maxsum[i][j];
    }
    int main()
    {
    	freopen("a.txt","r",stdin);
    	cin >> n;
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= i; ++j)
    		{
    			cin >> a[i][j];
    			maxsum[i][j] = -1;//等于-1说明没有计算过 
    		}
    	}
    	cout << SumMax(1,1);
    	return 0;
    }

用递推的方法解决问题：

![70 4][]

![70 5][]

#include<iostream>
    #define N 100
    using namespace std;
    int a[N][N];
    int n; 
    int summax[N][N];
    int main()
    {
    	freopen("a.txt","r",stdin);
    	cin >> n;
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= i; ++j)
    		{
    			cin >> a[i][j];
    		} 
    	}
    	for(int i = 1; i <= n; ++i)//从最后一行开始递推 
    		summax[n][i] = a[n][i];
    	for(int i = n-1; i >= 1; --i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			summax[i][j] = max(summax[i+1][j],summax[i+1][j+1]) + a[i][j];
    		}
    	}
    	cout << summax[1][1] << endl;
    	return 0;
    }

空间优化：

要点：只需要最后一行记录每次的和变化即可，因为不需要求出具体的路径，只需要知道最大和，所以每次用最后一行来更新最大和。

![70 6][]

![70 7][]

#include<iostream>
    #define N 100
    using namespace std;
    int a[N][N];
    int maxsum[N];//求最大和 
    int main()
    {
    	freopen("a.txt","r",stdin);
    	int n;
    	cin >> n;
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= i; ++j)
    		{
    			cin >> a[i][j];
    		}
    	}
    	for(int i = 1; i <= n; ++i)
    	{
    		maxsum[i] = a[n][i];
    	}
    	for(int i = n-1; i >= 1; --i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			maxsum[j] = max(maxsum[j],maxsum[j+1]) + a[i][j];
    		}
    	}
    	cout << maxsum[1] << endl;
    	return 0;
    }

![70 8][]

#include<iostream>
    #define N 100
    using namespace std;
    int a[N][N];
    //int maxsum[N];//求最大和 
    int *maxsum;
    int main()
    {
    	freopen("a.txt","r",stdin);
    	int n;
    	cin >> n;
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= i; ++j)
    		{
    			cin >> a[i][j];
    		}
    	}
    	/*
    	for(int i = 1; i <= n; ++i)
    	{
    		maxsum[i] = a[n][i];
    	}
    	*/
    	maxsum = a[n];//maxsum指向第n行 
    	for(int i = n-1; i >= 1; --i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			maxsum[j] = max(maxsum[j],maxsum[j+1]) + a[i][j];
    		}
    	}
    	cout << maxsum[1] << endl;
    	return 0;
    }

[70]: /images/20220504/9c5e875aa755445286592438fd2be082.png
[70 1]: /images/20220504/5dfdb812bc024bce98608c885a43188a.png
[70 2]: /images/20220504/557beacf5ab9473a9d054396bf6dde36.png
[70 3]: /images/20220504/5bc73da2c02e4705ac39db67d4d4c4bf.png
[70 4]: /images/20220504/8897a355ddac4fbab19c325dd149be4e.png
[70 5]: /images/20220504/1f26c7975dbf44149588933d6d6eff3f.png
[70 6]: /images/20220504/076ba1f589e340b79cff52d2cd6cf446.png
[70 7]: /images/20220504/b0913e730c10465494aaa41c8b4ebaa8.png
[70 8]: /images/20220504/15ccaab8e57d48999ba33990f3b7dd47.png