机试:数塔路径

问题描述:
代码示例:

//数塔路径
#include <bits/stdc++.h>using namespace std;int main(){
//	算法思想:
//	逆推,将最下方和右下方的数字进行比较,哪个大则加上并更新,直至到根节点即为最大 int n;cin >> n; int nums[n+1][n+1];
//	输入数塔 for(int i =1;i <= n;i++){for(int j = 1;j <= i;j++){cin >> nums[i][j];}}  //	更新各层节点到叶节点的最大值 for(int i = n - 1;i >= 1;i--){//从i-1层开始更新 for(int j = 1;j <= i;j++){if(nums[i+1][j] > nums[i+1][j+1]){//正下方 > 右下方 nums[i][j] += nums[i+1][j];//加上大的一个 } else{nums[i][j] += nums[i+1][j+1];//加上大的一个 }}} //	输出cout << "输出样例" << endl;cout << nums[1][1]; return 0;
}

运行结果: