求解惑 蓝桥杯 跳跃 python

Question

有大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])

Answer 1

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

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

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

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