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

化繁为简解决leetcode第1289题下降路径最小和II

news 来源：原创 2025/6/28 4:59:33

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)

运行实例一

pls input grid=[[3,2,1],[0,2,4],[4,3,1]]

所有非零偏移向下路径： [[0, 1, 0], [0, 1, 2], [0, 2, 0], [0, 2, 1], [1, 0, 1], [1, 0, 2], [1, 2, 0], [1, 2, 1], [2, 0, 1], [2, 0, 2], [2, 1, 0], [2, 1, 2]]

索引路径： [0, 1, 0] 和为： 9

最小和为： 9

索引路径： [0, 1, 2] 和为： 6

最小和为： 6

索引路径： [0, 2, 0] 和为： 11

最小和为： 6

索引路径： [0, 2, 1] 和为： 10

最小和为： 6

索引路径： [1, 0, 1] 和为： 5

最小和为： 5

索引路径： [1, 0, 2] 和为： 3

最小和为： 3

索引路径： [1, 2, 0] 和为： 10

最小和为： 3

索引路径： [1, 2, 1] 和为： 9

最小和为： 3

索引路径： [2, 0, 1] 和为： 4

最小和为： 3

索引路径： [2, 0, 2] 和为： 2

最小和为： 2

索引路径： [2, 1, 0] 和为： 7

最小和为： 2

索引路径： [2, 1, 2] 和为： 4

最小和为： 2

所有非零偏移下降路径最小和为： 2

运行实例二

pls input grid=[[2,1],[1,3]]

所有非零偏移向下路径： [[0, 1], [1, 0]]

索引路径： [0, 1] 和为： 5

最小和为： 5

索引路径： [1, 0] 和为： 2

最小和为： 2

所有非零偏移下降路径最小和为： 2

运行实例三

pls input grid=[[3]]

所有非零偏移向下路径： [[0]]

索引路径： [0] 和为： 3

最小和为： 3

所有非零偏移下降路径最小和为： 3

要善于化繁为简，把复杂问题分解为很多简单小问题，也许问题就不在有难度，大道至简！诚如斯言。

1289.下降路径最小和II

难度：困难

问题描述：

问题分析：

程序如下：

运行实例一

运行实例二

运行实例三

相关文章：