在excel中怎么做邮箱网站,好看的网站后台,wordpress 菜单栏调用,专业画册设计试题 H: 数字三角形【问题描述】上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径#xff0c;把路径上面的数加起来可以得到一个和#xff0c;你的任务就是找到最大的和。路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右…试题 H: 数字三角形【问题描述】上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径把路径上面的数加起来可以得到一个和你的任务就是找到最大的和。路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外向左下走的次数与向右下走的次数相差不能超过 1。【输入格式】输入的第一行包含一个整数 N (1 N ≤ 100)表示三角形的行数。下面的N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。【输出格式】输出一个整数表示答案。【样例输入】573 88 1 02 7 4 44 5 2 6 5【样例输出】27方法一思路(递归)利用递归的形式来完成从上到下的遍历首先创建函数fin(x,y,c,dx,dl) x,y表示q列表的位置c为累加的数dxdl分别表示左右走的步数。u[[1,0],[1,1]]左右位置让函数不断的递归所有位置的可能。时间复杂度均为o(2**n)0。程序aint(input())q[]for _ in range(a):q.append(list(map(int,input().split())))mx0u[[1,0],[1,1]]def fin(x,y,c,dx,dl):global mxfor i in range(2):dxu[i][0]lyu[i][1]if da:if mxmxcreturnelif i0:fin(d,l,cq[d][l],dx1,dl)else:fin(d,l,cq[d][l],dx,dl1)fin(0,0,q[0][0],0,0)print(mx)方法二思路(动态规划)DP推导奇偶判断。在输入数组的时候进行数组值的计算因为只能向左或者右走即我现在所在的位置坐标是从上一层这个位置的左边或者上边进行跳转得到的坐标通过选择最大值进行跳转更新数组的值由于向左向右不能超过1所以通过奇偶判断层数如果是奇数最后的位置第a层第(a//2)位置上的数字如果是偶数则需要判断第n层第(a/2-1)位置的数字和第a层第(a/2 )位置的数字选大的。注意我的数组下标是从0开始。程序aint(input())q[]for _ in range(a):q.append(list(map(int,input().split())))for i in range(a):for i1 in range(i):try :q[i][i1]max(q[i-1][i1-1],q[i-1][i1])except:if i10:q[i][i1]q[i-1][i1]else:q[i][i1]q[i-1][i1-1]print(q[a-1][int(a/2)] if a%21 else max(q[a-1][a/2-1],q[a-1][a/2]))禁止转载。仅用于自己学习。对程序错误不负责。
