欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蓝桥杯 ALGO-124 数字三角形

程序员文章站 2024-02-21 18:46:40
...

蓝桥杯 ALGO-124 数字三角形

题意:给定一个数字三角形,求从顶部到底部的可以形成的最大的和,只能先左下角和右下角走。对应的三角形走法只能是向下和向右下角走。

思路:此题也是一个递归的问题,从顶部开始,然后向下和向右下角走,所以得到的递推式为:d[i][j] = a[i][j]+max(sum(i+1,j),sum(i+1,j+1));//到底部时候就向上返回其结果,而且要加上当前的值。

递归出口为:d【i】【j】>=0(表示当前已经经过处理,而不是原始的数据),i==n(已经到达底部,直接返回其值)

代码:

#include <iostream>
#include<algorithm>
using namespace std;
int a[101][101],d[101][101],n;//a保存的是矩阵三角形,d是保存的结果 
int sum(int i,int j){//i表示的是横坐标,j表示的是纵坐标 
	if(d[i][j]>=0){//递归的两个出口 
		return d[i][j];	
	}
	if(i==n){
		return a[i][j];
	}
	return d[i][j] = a[i][j]+max(sum(i+1,j),sum(i+1,j+1));//递归部分当前和等于左边节点的和与右边节点的和的较大值 
}
int main(int argc, char** argv) {
	fill(d[0],d[0]+101*101,-1);//初始化 
	cin >> n;
	for (int i = 1; i <= n; i++) {//给矩阵元素赋值 
		for (int j = 1; j <= i; j++) {
			cin >> a[i][j];
		}
	}
	cout << sum(1,1);
	return 0;
}