蓝桥杯 ALGO-124 数字三角形
程序员文章站
2024-02-21 18:46:40
...
题意:给定一个数字三角形,求从顶部到底部的可以形成的最大的和,只能先左下角和右下角走。对应的三角形走法只能是向下和向右下角走。
思路:此题也是一个递归的问题,从顶部开始,然后向下和向右下角走,所以得到的递推式为: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;
}