这谁有思路？看一下吧

Question

谁知道这怎么写？
想了半天，它说用二维数组，但咋做？谁来讲一下？
传送门：https://qqwhale.com/group/999/training/10293/problem/8222

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

问题描述： 给定一个n行m列的矩形，每个格子里有一个数字。现在要计算一条起点在矩形的左上角，终点在矩形的右下角的路径，其经过的数字之和最小。其中，路径需满足只能向下或向右移动。 解答： 此题可以用动态规划来解决。我们可以定义一个二维数组dp，表示从起点到达第i行第j列的最小路径和。则有转移方程： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j] 其中，a[i][j]表示矩形中第i行第j列的数字。 边界条件为dp[0][0] = a[0][0]，dp[0][j] = dp[0][j-1] + a[0][j]，dp[i][0] = dp[i-1][0] + a[i][0]。 最后，答案即为dp[n-1][m-1]。 以下是Python代码实现： n, m = map(int, input().split()) a = [] for i in range(n):

a.append(list(map(int, input().split())))

初始化dp数组

dp = [[0]*m for i in range(n)] dp[0][0] = a[0][0] for i in range(1, n): dp[i][0] = dp[i-1][0] + a[i][0] for j in range(1, m): dp[0][j] = dp[0][j-1] + a[0][j]

动态规划

for i in range(1, n): for j in range(1, m): dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j] print(dp[n-1][m-1])