python學習之路——DP演算法初試

這次的題目是這樣的：

　　假設有一個6*6的棋盤，每個格子裡面有一個獎品（每個獎品的價值在100到1000之間），現在要求從左上角開始到右下角結束，每次只能往右或往下走一個格子，所經過的格子里的獎品歸自己所有。問最多能收集價值多少的獎品。

　　最先看到這個問題的時候腦子裡面的立馬出現許多的腦洞：暴力、二叉樹、圖中的帶權路徑等等。但是想來想去沒有想出個所以然來。偶然在一本演算法書上看見了講DP演算法(動態規劃)的部分，仔細一想，貌似能夠用在這裡的。

　　DP演算法適用於前一步的決策影響後一步決策的問題中。本題藍色方塊的決策取決於其左邊和上面的最優決策，因此，對於藍色部分a[i][j]只需要取max{a[i-1][j],a[i][j-1]}+a[i][j];對於白色部分，只受左邊或者上面的決策影響，因此對於橫向的a[i][j]應該取a[i][j-1]+a[i][j],對於縱向的a[i][j]應該取a[i-1][j]+a[i][j]。其實DP能夠解決的問題還有很多，我相信這也是一個特別有用的演算法，強烈建議閱讀學習使用。

tips：代碼中涉及python中二維數組的初始化和賦值，可以用列表推導式初始化。

代碼：

 1 import random
 2 count=0
 3 a=[[0 for i in range(6)]for i in range(6)]
 4 print("隨機生成一個6*6的二維數組做為棋盤中的權值：")
 5 for i in range(6):
 6     for j in range(6):
 7         a[i][j] = random.randint(100, 1000)
 8         print('%2d'%a[i][j],end=" ")
 9         count+=1
10         if count%6==0:
11             print("\n")
12 for i in range(1,6):
13     a[0][i]=a[0][i-1]+a[0][i]
14     a[i][0]=a[i-1][0]+a[i][0]
15 for i in range(1,6):
16     for j in range(1,6):
17         a[i][j]=max(a[i-1][j],a[i][j-1])+a[i][j]
18 print("變化後的數組：")
19 for i in range(6):
20     for j in range(6):
21         print('%2d'%a[i][j],end=" ")
22         count+=1
23         if count%6==0:
24             print("\n")
25 print("最終得最大值為%d" %a[5][5])

運行結果：

　　　　當然，在自己做出來之前，不免詢問了一下我們的度娘，也得到了一種暴力解法，無奈用的遞歸解決的，太暴力太燒腦，想了好久都沒想通，這裡將原c++版的代碼改寫成了python的代碼供大家學習思考。

#6*6的棋盤求最大路徑
import random
global count
totalprice=0
tmp=0
count=0
a=[[0 for i in range(6)]for i in range(6)]
b=[[0 for i in range(6)]for i in range(6)]
next=[[1,0],[0,1]]
def find(x, y):
    global totalprice
    global tmp
    totalprice+=a[x][y]
    if x==5 and y==5:
        if totalprice>tmp:
            tmp=totalprice
            return
    for k in range(2):
        tx=x+next[k][0]
        ty=y+next[k][1]
        if tx<0 or tx>5 or ty<0 or ty>5:
            continue
        if b[tx][ty]==0:
            b[tx][ty]=1
            find(tx,ty)
            totalprice-=a[tx][ty]
            b[tx][ty]=0
    return
for i in range(6):
    for j in range(6):
        a[i][j] = random.randint(1, 100)
        print('%2d'%a[i][j],end=" ")
        count+=1
        if count%6==0:
            print("\n")
b[0][0]=1
find(0,0)
print(tmp)