秃头小二 2023-03-08 20:08 采纳率: 100%
浏览 46
已结题

求解惑 蓝桥杯 跳跃 python

有大lao能帮我分析下题目以及我贴出的代码吗?感激不尽!
或者直接回答我最直接的一个疑问就是:
为什么是减而不是加(也就是为啥向上和左走),我搞不清楚其中的逻辑
迷迷糊糊的

x = i - dx # 为啥是减,计算上一步的权值?
y = j - dy

题目链接在下面↓
https://www.lanqiao.cn/problems/553/learning/?page=1&first_category_id=1&sort=students_count&second_category_id=3&status=1&difficulty=30&tags=DFS,BFS,%E6%90%9C%E7%B4%A2,%E9%80%92%E5%BD%92,%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2,%E4%BA%8C%E5%88%86,%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE

# 跳跃
n,m = map(int,input().split())
dp = [list(map(int,input().split())) for _ in range(n)]
index_move = [(0,1),(0,2),(0,3),(1,0),(2,0),(3,0),(1,2),(2,1),(1,1)] # 只可以往右和下走
# 为啥(2,2)不可以? ---> 貌似是出题人的问题,不用计较

for i in range(n):
    for j in range(m):
        res = [] # 存储下一步能走的位置的权值
        for dx, dy in index_move:
            # 向上/左
            x = i - dx # 为啥是减,计算上一步的权值?逆向操作吗?
            y = j - dy
            if 0 <= x < n and 0 <= y < m:
                res.append(dp[x][y])
        dp[i][j] += max(res) if res else 0 # 添加权值最大值(每次走的这一步都是最优解)
        for k in dp:
            print(k)
        print()
print(dp[-1][-1])
  • 写回答

3条回答 默认 最新

  • 是小闫同学 2023-03-08 21:28
    关注

    这个代码实现了一个动态规划来求解跳跃问题,但是在代码最后还缺少一个 print 语句来输出结果。下面对代码进行一些解释和修改建议:

    首先需要注意的是,这个问题是一个动态规划问题,而不是贪心问题。因为在走每一步的时候,需要综合之前所有步的结果来确定最优解。因此在计算 dp[i][j] 的值的时候,需要遍历之前所有的可达位置,取其中权值最大的一个。

    在计算 dp[i][j] 的时候,遍历的是之前所有的可达位置,因此这些位置都是在上一轮中已经计算出来的,可以直接使用 dp 数组中的值,而不需要再计算一遍。

    原代码在遍历可达位置的时候,采用的是逆向操作,也就是计算上一步的权值。这样做可以保证在遍历之前所有的可达位置的时候,它们的值都是已知的,从而可以取最大值。如果采用正向操作,在遍历到某个位置时,它前面的位置的值可能还没有计算出来,这样就无法得到最优解。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 3月17日
  • 已采纳回答 3月9日
  • 创建了问题 3月8日

悬赏问题

  • ¥15 高缺失率数据如何选择填充方式
  • ¥50 potsgresql15备份问题
  • ¥15 Mac系统vs code使用phpstudy如何配置debug来调试php
  • ¥15 目前主流的音乐软件,像网易云音乐,QQ音乐他们的前端和后台部分是用的什么技术实现的?求解!
  • ¥60 pb数据库修改与连接
  • ¥15 spss统计中二分类变量和有序变量的相关性分析可以用kendall相关分析吗?
  • ¥15 拟通过pc下指令到安卓系统,如果追求响应速度,尽可能无延迟,是不是用安卓模拟器会优于实体的安卓手机?如果是,可以快多少毫秒?
  • ¥20 神经网络Sequential name=sequential, built=False
  • ¥16 Qphython 用xlrd读取excel报错
  • ¥15 单片机学习顺序问题!!