贪心算法、递推-数塔问题

本文主要是介绍贪心算法、递推-数塔问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述

有如下所示的数塔，要求从底层走到顶层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

输入格式

输入数据首先包括一个整数整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。

输出格式

从底层走到顶层经过的数字的最大和是多少？

样例输入

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

样例输出

30

题解

1.找规律
贪心算法：找到当前最优
将最后一层最优值加到上一层
递归
2.建模
将数塔转变为数据结构
怎么知道一个值，立刻就知道其下的两个值
二位数组：值、层级关系

a[x,y]+=max{ a[x+1][y],a[x+1][y+1]}

      7+23
    3+20 8+13
  8+12 1+12 0+10
 2+5  7+5  4+6  4+6
4    5    2    6     5
-------------

3.代码实现

#include<iostream>
#include <algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[n+1][n+1] ;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
		}
	}
	for(int i=n-1;i>0;i--)
		for(int j=1;j<=i;j++){
			a[i][j]+=max(a[i+1][j],a[i+1][j+1]);		
			}	 
	cout<<a[1][1]; 
	return 0; 
} 

这篇关于贪心算法、递推-数塔问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！