題目：棋盤如下，每個棋盤的代價不同，每次只能向下走或者向右走，以最小的代價從左上角走到右下角，記錄走的路徑，該怎么走？

分析：
1. 關于怎么走
1). 第一行的棋格，除了第一個棋格，都是它左邊的棋格向右走得到的。
2). 第一列的棋格，除了第一個棋格，都是它上邊的棋格向下走得到的。
3). 棋盤中的剩余的棋格，要么從左邊，要么從上邊走過來，到底從哪過來，就要看這二者的大小.
4). dp記錄代價。dp[i][j]走到（i，j）的最小代價
2. 關于路徑記錄
1). location數(shù)組用來記錄走到當前位置的上一步在哪。比如（1,1）的5從（1,0）的2走過來，所以location[1][1]=[1,0]
2). 當location數(shù)組填完后，需要根據(jù)右下角元素回溯，找到最短路徑。
3). location[i][j]到達（i，j）的上一步在哪

import numpy as np ''' 走棋盤，每個棋盤的代價不同，以最小的代價從左上角走到右下腳，記錄走的路徑。 dp[i][j]走到（i，j）的最小代價 location[i][j]到達（i，j）的上一步在哪 ''' arr = np.array([[10,3,1],[2,8,5],[20,7,12]]) dp=np.zeros(arr.shape) location=[[ 0 for i in range(3)]for j in range(3)]# 數(shù)組形式。numpy數(shù)組不能賦列表 location[0][0]=[0,0] # print(location) dp[0][0]=arr[0][0]n = arr.shape[0]# 行數(shù) m = arr.shape[1]# 列數(shù)for i in range(m-1):dp[0, i+1] = dp[0, i]+arr[0, i+1]location[0][i+1]=[0,i] for i in range( n- 1):dp[i+1, 0] = dp[i, 0]+arr[i+1, 0]# location[i+1][0].append([i, 0])location[i+1][0]=[i, 0]for i in range(1,n):for j in range(1,m):if dp[i-1][j] < dp[i][j-1]:dp[i][j] = dp[i - 1][j]+ arr[i][j]# location[i][j]=append([i-1,j])location[i][j]=[i-1,j]else:dp[i][j] = dp[i][j- 1] + arr[i][j]location[i][j]=[i,j- 1]# dp[i][j]=min(dp[i-1][j],dp[i][j-1])+arr[i][j]print('總代價為：',dp[2][2]) print('代價矩陣：\n',dp) # print(location) # print(location[2][2]) n = len(location)-1 m = len(location[0])-1l = [] l.append([n, m]) while not(n==0 and m==0):a = location[n][m]# print(location[n][m])n=location[n][m][0]m=location[n][m][1]l.append([n, m])# print(n,m)l.reverse()# 遍歷順序 print('走的路徑為:') for i,loc in enumerate(l):if i == len(l)-1:print(loc)breakprint(loc,end='——>') 總代價為： 31.0 代價矩陣：[[10. 13. 14.][12. 20. 19.][32. 27. 31.]] 走的路徑為: [0, 0]——>[0, 1]——>[1, 2]——>[2, 2]

總結(jié)

以上是生活随笔為你收集整理的走棋盘——最小代价的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。