天威难测

用户名：uq_61498387617

访问量：1331

签　名：

岁月在你我呼吸间流浪

等　　级
排　　名	8300
经　　验	1240
参赛次数	1
文章发表	10
年　　龄	0
在职情况	学生
学　　校	南京中医药大学
专　　业	中药学类

　　自我简介：

TA的其他文章

利用最大公因数来求解
浏览：104

就很简单的原理
浏览：138

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

A+B for Input-Output Practice (V) （C++代码）

动态规划与优化后的动态规划哈哈哈哈

　　作者: 天威难测　　　　发表时间：2022-02-23 12:54:01 浏览：676　|　评论：0　

原题链接：蓝桥杯算法提高VIP-夺宝奇兵

# 问题描述

![在这里插入图片描述](https://img-blog.csdnimg.cn/5e9a47cfa37b4198ac82ff9047a2b47b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5aSp5aiB6Zq-5rWL,size_20,color_FFFFFF,t_70,g_se,x_16)

# 思路描述
其实和之前做的“数字三角形”那道题目差不多啦，也是从上往下遍历，定义一个从这个数开始保存最大数的列表，具体思路可以看我之前的文章：

https://blog.csdn.net/m0_53347750/article/details/122472202

# 源码
同样的，这道题目用简单的动态规划是不行的：

```python
# dp
def dp(x, y):
    global value
    global n
    
    if(x == n - 1):
        return(value[x][y])

else:
        
        temp_1 = dp(x + 1, y)
        temp_2 = dp(x + 1, y + 1)

if(temp_1 > temp_2):
            return(temp_1 + value[x][y])
        else:
            return(temp_2 + value[x][y])

# main
global value
global n

n = int(input())
value = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    line = input().split()

for j in range(len(line)):
        value[i][j] = int(line[j])

print(dp(0, 0))

```
需要中间新定义一个列表来保存数据，达到一个重复利用的效果

```python
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))

```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

天威难测

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

模拟计算器（C语言代码）

A+B for Input-Output Practice (V) （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

动态规划与优化后的动态规划哈哈哈哈

评论区

精彩推荐

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-小九九（C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

C二级辅导-阶乘数列（C语言代码）

剪刀石头布（C语言代码）

计算质因子（C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

天威难测

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

模拟计算器 （C语言代码）

A+B for Input-Output Practice (V) （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

动态规划与优化后的动态规划哈哈哈哈

评论区

精彩推荐

【亲和数】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-小九九 （C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

剪刀石头布 （C语言代码）

计算质因子 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

模拟计算器（C语言代码）

　　评论区

【亲和数】（C语言代码）

WU-小九九（C++代码）

C二级辅导-阶乘数列（C语言代码）

剪刀石头布（C语言代码）

计算质因子（C语言代码）