Java教程

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

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

题目描述

有如下所示的数塔,要求从底层走到顶层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?
在这里插入图片描述

输入格式

输入数据首先包括一个整数整数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; 
} 
这篇关于贪心算法、递推-数塔问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!