【蓝桥杯】【python】数字三角形

2021-10-02 02:18:21

问题描述

虽然我前后用了三种做法，但是我发现只有“优化思路_1”可以通过蓝桥杯官网中的测评，但是如果用c/c++的话，每个都通得过，足以可见python的效率之低（但耐不住人家好用啊（哭笑））

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

输入格式

输入的第一行包含一个整数 N(1<N<=100)，表示三角形的行数。下面的N行给出数字三角形。数字三角形上的数都是0至100之间的整数。

输出格式

输出一个整数，表示能够达到的最大值

示例

此时输出 30

最初思路

数字三角形的输入

首先创建一个名为triangle的二维列表，并将其设置成全局变量。

triangle = [[0 for i in range(n)] for j in range(n)]

然后利用两个for循环，先是输入一个列表并将其断裂后一个个输入二维列表中

for i in range(n):
    line = input().split()
    for j in range(i + 1):
        triangle[i][j] = int(line[j])

定义寻最值的函数

定义一个函数MaxSum(i, j)，主要利用递归的方法吗，用于寻找triangle[i][j]这个元素，到数字三角形最底部时获得的最大值。

def MaxSum(i, j):
    '''利用递归求解triangle[i][j]到数组最后一列的最大值'''
    global triangle
    global n
    if(i == n - 1):
        return triangle[i][j]
    else:
        sum1 = MaxSum(i + 1, j)
        sum2 = MaxSum(i + 1, j + 1)
        if(sum1 > sum2):
            return(sum1 + triangle[i][j])
        else:
            return(sum2 + triangle[i][j])

完整代码及其不足

global triangle
global n

def MaxSum(i, j):
    '''利用递归求解triangle[i][j]到数组最后一列的最大值'''
    global triangle
    global n
    if(i == n - 1):
        return triangle[i][j]
    else:
        sum1 = MaxSum(i + 1, j)
        sum2 = MaxSum(i + 1, j + 1)
        if(sum1 > sum2):
            return(sum1 + triangle[i][j])
        else:
            return(sum2 + triangle[i][j])

# main()
n = int(input())
# 创建一个二维列表
triangle = [[0 for i in range(n)] for j in range(n)]
# 输入二维列表中的数字
for i in range(n):
    line = input().split()
    for j in range(i + 1):
        triangle[i][j] = int(line[j])

print(MaxSum(0, 0))

在评测时发现数字限制少尚且没事，如果变大则会超时，所以加以优化得到如下新思路

优化思路_1

将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，可以称为“动态规划”。动态规划通常用来求最优解。

能用动态规划解决的求最优解问题，必须满足最优解的每个局部解也都是最优的。以上题为例，最佳路径中的每个数字到底部的那一段路径，都是从该数字出发到底部的最佳路径。

原文链接：https://blog.csdn.net/qq_41045071/article/details/83062999

global triangle
global n

def MaxSum(i,j):
    global n
    global triangle
    if i == n - 1:
        return triangle[i][j]
    if(maxSum[i + 1][j] == -1):
        maxSum[i + 1][j] = MaxSum(i + 1, j)
    if (maxSum[i + 1][j + 1] == -1):
        maxSum[i + 1][j + 1] = MaxSum(i + 1, j + 1)
    if(maxSum[i + 1][j] > maxSum[i + 1][j + 1]):
        return maxSum[i + 1][j] + triangle[i][j]
    return maxSum[i + 1][j + 1] + triangle[i][j]
    
# main()
n = int(input())
# 创建一个二维列表
triangle = [[0 for i in range(n)] for j in range(n)]
# 输入二维列表中的数字
maxSum=[[0 for s in range(n)]for k in range(n)]
# maxSum用于保存最优值
# 将maxSum中的值全部设置成-1
for s in range(n):
    for k in range(s + 1):
        maxSum[s][k] = -1

for i in range(n):
    line = input().split()
    for j in range(i + 1):
        triangle[i][j] = int(line[j])

print(MaxSum(0, 0))

按照我的理解，就是另外定义一个数组，是这个数组用于保存对应在triangle列表中那个值到最底部的最大结果。
这样可以在后期再用到时进行重复利用，而不是像最初思路那样进行重复计算。

优化思路_2

实际上，递归的思想在编程时未必要实现为递归函数，有递推公式

MaxSum( r , j ) = d( r , j ) ,当且仅当 r = N ；MaxSum（ r , j ）= Max { MaxSum( r+1 , j ) , MaxSum( r+1 , j+1 ) } + d ( r , j ) , 其他；

不需要写递归函数，从maxSum[ N -1 ]这一行元素开始向上逐行递推，就能求得最终maxSum[ 1 ][ 1 ]的值。程序如下：

global triangle
global n

def MaxSum(i,j):
    global n
    global triangle
    if i==n-1:
        return triangle[i][j]
    else:
        return(max(MaxSum(i + 1, j), MaxSum(i + 1, j + 1)) + triangle[i][j])

# main()
n = int(input())
# 创建一个二维列表
triangle = [[0 for i in range(n)] for j in range(n)]
# 输入二维列表中的数字
maxSum=[[0 for s in range(n)]for k in range(n)]
#maxSum用于保存最优值
for s in range(n):
    for k in range(s + 1):
        maxSum[s][k] = -1

for i in range(n):
    line = input().split()
    for j in range(i + 1):
        triangle[i][j] = int(line[j])

print(MaxSum(0, 0))

但是吧，，，这样还是不能通过测评

码农公寓