数字三角形【动态规划(含手工运算及多种源码)】_数字三角形问题动态规划

目录

1.问题描述

2.解题思路

3.手工运算

4.空间优化

5.完整源码

（1）从下到上DP

（2） DP，记录路径

（3）从上到下DP

---

1.问题描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

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

---

2.解题思路

用二维数组存放数字三角形。

D( r, j)︰第r行第j个数字(r,j从1开始算)

MaxSum(r. j):从D(r,j)到底边的各条路径中，最佳路径的数字之和。

问题:求MaxSum(1,1) 

典型的递归问题。

D(r, j)出发，下一步只能走D(r+1,j)或者D(r+1,j+1)。

这种方法的思想是正确的，它有一个名字叫做递归，但是采用递规的方法，深度遍历每条路径，存在大量重复计算。则时间复杂度为2^n,对于n = 100行，肯定超时。

我们如何对其进行改进呢

如果每算出一个MaxSum(r,j)就保存起来，下次用到其值的时候直接取用，则可免去重复计算。那么可以用O(n2)时间完成计算。因为三角形的数字总数是n(n+1)/2

---

3.手工运算

我们将最底部的数字填入表格中

根据题意，我们要将最后一行与倒数第二行相加的最大值填入表格，题目要求上面那一行的数字只能和他正下方那个数字或者是与他右下方的那个数字相加，取两者的较大值代替那个数字。这也就是动态规划的思想

 

 

 

---

4.空间优化

没必要用二维maxSum数组存储每一个MaxSum(r,j),只要从底层一行行向上递推，那么只要一维数组maxSum[100]即可,即只要存储一行的MaxSum值就可以。

 

 

 

 

---

5.完整源码

（1）从下到上DP

#include<iostream>
#include<cmath>
using namespace std; 
int a[1003][1003];
int ans[1003][1003];
int main()
{
	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=n;i>=1;i--)
	{
		for(int j=1;j<=i;j++)
		{
			ans[i][j]=max(ans[i+1][j],ans[i+1][j+1])+a[i][j];
		}
	}
	
	//输出 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cout<<ans[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

---

（2） DP，记录路径

#include<iostream>
#include<cmath>
using namespace std; 
int a[1003][1003];
int lu[1003];
int ans[1003][1003];
int main()
{
	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++)
	{
		for(int j=1;j<=i;j++)
		{
			ans[i][j]=max(ans[i-1][j-1],ans[i-1][j])+a[i][j];
		}
	}
	//从下到上返回路径 
	int l=0;
	for(int i=1;i<=n;i++)//找到最后一行最大路径所在位置 
	{
		if(ans[n][i]>ans[n][l])l=i;
	}
	for(int i=n;i>=1;i--)
	{
		if(ans[i][l]>ans[i][l-1])
		{
			lu[i]=a[i][l];
		}
		else
		{
			lu[i]=a[i][l-1];
			l--; 
		}
	}
	
	//从下往上 
	/*for(int i=n;i>=1;i--)
	{
		for(int j=1;j<=i;j++)
		{
			ans[i][j]=max(ans[i+1][j],ans[i+1][j+1])+a[i][j];
		}
	}
	//从上到下返回路径 
	int l=1;
	for(int i=1;i<=n;i++)
	{
		if(ans[i][l]>ans[i][l+1])
		{
			lu[i]=a[i][l];
		}
		else
		{
			lu[i]=a[i][l+1];
			l++;
		}
	}*/
	
	//输出 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cout<<ans[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<"路径：";
	for(int i=1;i<=n;i++)
	{
		cout<<lu[i]<<" ";
	}
	cout<<endl;
	return 0;
}

---

（3）从上到下DP

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
vector<int> D(505, 0);
vector<int> pre(505, 0);
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=i; j++)
        	scanf("%d", &D[j]);	
    	for(int j=i; j>=1; j--)
        {
        	if(j==1)
        		pre[j]=pre[j];
        	else if(j==i)
        		pre[j]=pre[j-1];
        	else
        		pre[j]=max(pre[j-1], pre[j]);
            pre[j]=D[j]+pre[j];
        }
    }
    printf("%d\n", *max_element(pre.begin()+1, pre.begin()+n+1));
    return 0;
}