当前位置：首页 > news >正文

asp.net做网站推荐书籍/百度平台营销收费标准

news 2025/7/6 10:38:30

asp.net做网站推荐书籍,百度平台营销收费标准,wordpress创建主题,东莞市的网站公司哪家好1289.下降路径最小和II 难度：困难问题描述： 给你一个nxn整数矩阵grid，请你返回非零偏移下降路径数字和的最小值。非零偏移下降路径定义为：从grid数组中的每一行选择一个数字，且按顺序选出来的数字中，…

1289.下降路径最小和II

难度：困难

问题描述：

给你一个nxn整数矩阵grid，请你返回非零偏移下降路径数字和的最小值。

非零偏移下降路径定义为：从grid数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

示例1：

输入：grid=[[1,2,3],[4,5,6],[7,8,9]]

输出：13

解释：

所有非零偏移下降路径包括：

[1,5,9],[1,5,7],[1,6,7],[1,6,8],

[2,4,8],[2,4,9],[2,6,7],[2,6,8],

[3,4,8],[3,4,9],[3,5,7],[3,5,9]

下降路径中数字和最小的是[1,5,7]，所以答案是13。

示例2：

输入：grid=[[7]]

输出：7

提示：

n==grid.length==grid[i].length

1<=n<=200

-99<=grid[i][j]<=99

问题分析：

对于非零偏移下降路径，只要考虑当前的一步，这一步是nXn矩阵中的一个索引值，比如n=4，这一步的索引值为2，则下一步的索引值只能取[0,1,3]中的一个，总的来看，下降路径的第一步可以在[0,1,2,...,n-1]选择，共有n种选择，从第二步到第n步都只有n-1种选择，所有总的下降路径共有n*(n-1)*(n-1)...*(n-1)种，即n*(n-1)**（n-1）种。对于一个4阶矩阵，下降路径共有4*3*3*3共108种。

把所有的非零偏移下降路径找到之后，对于其中的每一种路径，根据索引值依次找到矩阵中对应元素的值，求出其和，然后找出其中的最小值输出即可。

为此，对于一个nxn矩阵，为了找到所有非零偏移下降路径，我们将这个问题分解为几个小问题，分别进行处理，然后再组合起来，实现这一功能。

第一步是对于一个索引值，我们如何找到下一步的非零偏移索引值，为此设计函数get_different_nums(n,i)，此函数功能是对有n个元素的列表，根据上一步索引值i，找出下一步的非零偏移索引值，并形成列表返回。

第二步是对于一个给定的nxn矩阵、已经形成路径K和向下产生的非零偏移索引值，将已经形成的路径 k与向下产生的非零偏移索值组成新的路径，为此设计函数 get_one_step_group(n,k)，n表示索引值有n个，k表示已经生成的向下非零偏移路径。

第三步是在n个元素的索引值列表[0,1,2,......,n-1]中选一个索引值，生成由这个索引值开始的非零偏移下降路径列表，为此设计函数get_one_all(n,i)，其中的i表示下降路径的第一个索引值。

第四步是生成所有的非零偏移下降路径列表，为此设计函数get_all_down_path(n)。

第五步是设计计算求一条非零偏移向下路径的和并返回的函数get_one_path_sum(path,grid)，path是一条非零偏移下降路径，grid是一个nxn矩阵。

最后根据所有的路径，依次求出每一条路径的元素和，并输出其最小值，问题得以解决。

程序如下：

#已知索引值[0,1,...n-1]中的一个索引值i，找出与这个索引值不同的所有索引值并以列表返回
def get_different_nums(n,i):b=list(range(n))b.remove(i)return b#对于一个给定的nxn矩阵，找到已经形成的路径K与下一步非零偏移索引值组成的所有新路径
def get_one_step_group(n,k):a=[]for i in k:c=i[-1]b=get_different_nums(n,c)for j in b:d=i+[j]a.append(d)return a#找出从索引值i开始在矩阵nXn中所有不同的非零偏移下降组合
def get_one_all(n,i):a=[[i]]for j in range(n-1):b=get_one_step_group(n,a)a=breturn a#对于一个nxn矩阵，找到所有非零偏移下降路径
def get_all_down_path(n):a=[]for i in range(n):b=get_one_all(n,i)a.extend(b)return a#求一条非零偏移向下路径的和并返回
def get_one_path_sum(path,grid):n=len(grid)a=list(range(n))b=list(zip(a,path))min_sum=0for i in b:min_sum=min_sum+grid[i[0]][i[1]]return min_sum#主程序
grid=eval(input('pls input grid='))
#取得所有非零向下偏移路径
a=get_all_down_path(len(grid))
print('所有非零偏移向下路径：',a)
#将取得的所有非零向下偏移路径中的第一条路径和求出并赋值给min_sum
print('索引路径：',a[0],end='     ')
min_sum=get_one_path_sum(a[0],grid)
print('和为：',min_sum)
print('最小和为：',min_sum)
#遍历剩下的所有路径并求和，找出最小和
for i in a[1:]:b=get_one_path_sum(i,grid)print('索引路径：',i,end='     ')print('和为：',b)if b<min_sum:min_sum=bprint('最小和为：',min_sum)
#打印最小和
print('所有非零偏移下降路径最小和为：',min_sum)