Python获取最小路径，查找元素在list中的坐标

# coding=utf-8

__author__ = 'Jeff.xie'

def t(li):

pass

获取最小路径

def minPathSum(grid):

if not grid:

return 0

m= len(grid) #m列

n =len(grid[0]) #n行

print(grid[0])

print("m: ",m)

print("n: ",n)

#创建一个二维数组

dp = [[0]*n for _ in range(m)]

print(dp) #这是一个所有值为0的二维数组

dp[0][0] = grid[0][0]#初始化左上角

#初始化第一列,最小和只能从上面到达，且需要加上当前格子的元素值

for i in range(1,m):

dp[i][0] = dp[i-1][0]+grid[i][0]#每一行的第一个元素，得到结果，并且是从原始数据的每一行第一个数据一次累加

print(dp)

#初始化第一行，最小和只能从左边到达，且需要加加上当前格子元素的最小值

for i in range(1,n):

dp[0][i] = dp[0][i-1] + grid[0][i]

print(dp)

#遍历其他地方的格子,路径只能从相邻左方和相邻上方到达，然后比较两者中最小的元素值加上当前网格的值

for i in range(1,m):

for j in range(1,n):

dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j] #判断是上边dp[i-1][j]的数据小，还是左边dp[i][j-1]的数据小

print(dp)

return dp[-1][-1]

查找元素在list中的坐标

def searchRange( nums, target):

#在排序数组中查找元素的第一个和最后一个位置

left = -1

right = -1

for i in range(len(nums)):

if nums[i] == target:

left = i

break

if left != -1:

for i in range(left, len(nums)):

if nums[i] == target:

right = i

return [left, right]

def t5(grid):

#获取行和列

row=len(grid)

column = len(grid[0])

print(column)

#初始化一个全部值为0，但是行列都相同的li

li = [[0]*column for i in range(row)] #总共有len(row)行，每一行都是一个list,每个list的元素都赋值为0

print(li)

#初始化左上角

li[0][0]= grid[0][0]

#初始化第一列

for i in range(1,row):

li[i][0]=li[i-1][0]+grid[i][0]

print(li)

#初始化第一行

for i in range(1,column):

li[0][i]= li[0][i-1]+grid[0][i]

print(li)

#填充其他单元格

for i in range(1,row):

for j in range(1,column):

x= min(li[i-1][j],li[i][j-1])

li[i][j]= x+grid[i][j]

print(li)

#最后一个数字就是最小路径

return li[-1][-1]

if __name__ == '__main__':

grid = [[1,3,1],[1,5,1],[4,2,1],[2,3,4]]

# r= minPathSum(grid)

# print(r)

# r= t2(grid)

# print(r)

r3=t3(grid)

print("r3:",r3)

li=[1,2,3,4,5,5,6,7]

r=searchRange(li,6)

print(r)

t5(grid)