就是從左上角到右下角，中間經過的權重選擇要是最大的，最後路徑權重的累加和是所有可能情況裡面最大的，有圖論的意思在裡面了。
% 題目來源：劍指 Offer 47: 禮物的最大價值
M = [5 1 5 1;
3 5 3 5;
4 2 1 1;
1 5 1 3;
1 5 3 4];
function f = max_gift_value1(M)
% 輸入的M就是棋盤中每個禮物的價值
[m,n] = size(M); % 棋盤m行n列
FF = M; % 初始化DP數組和M完全相同，用來保存f(i,j)
% 計算FF的第一列
FF(:,1) = cumsum(M(:,1)); % cumsum函數用來計算累加和
% 計算FF的第一行
FF(1,:) = cumsum(M(1,:));
% 循環計算右下部分的元素
for i = 2:m
for j = 2:n
tem1 = FF(i,j-1) + M(i,j); % 從左邊來
tem2 = FF(i-1,j) + M(i,j); % 從上面來
FF(i,j) = max(tem1,tem2);
end
end
f = FF(m,n);%累加的最後一個總和
end
>>>>>>>>>>>>>>>>輸出>>>>>>>>>>>>>>>>>>>>
f =
32
import numpy as np
matrix= np.array([[5,1,5,1],
[3,5,3,5],
[4,2,1,1],
[1,5,1,3],
[1,5,3,4]],
dtype=int)
a,b=matrix.shape
Matrix=matrix
Matrix[:,0]=np.cumsum(Matrix[:,0],axis=0,dtype=int)
Matrix[0,:]=np.cumsum(Matrix[0,:],axis=0,dtype=int)
i=0
j=0
for i in range(1,a):
for j in range(1,b):
num1 = Matrix[i][j]+Matrix[i-1][j]#left
num2 = Matrix[i][j]+Matrix[i][j-1]#up
Matrix[i][j]=max(num1,num2)
print("最大值是", Matrix[a-1][b-1])
print("整個矩陣是",Matrix)
##############輸出###############
最大值是 32
整個矩陣是
[[ 5 6 11 12]
[ 8 13 16 21]
[12 15 17 22]
[13 20 21 25]
[14 25 28 32]]
#############################
function [f,path] = max_gift_value2(M)
% 輸入的M就是棋盤中每個禮物的價值
[m,n] = size(M); % 棋盤m行n列
FF = M; % 初始化DP數組和M完全相同，用來保存f(i,j)
% 計算FF的第一列
FF(:,1) = cumsum(M(:,1)); % cumsum函數用來計算累加和
% 計算FF的第一行
FF(1,:) = cumsum(M(1,:));
% 循環計算右下部分的元素
for i = 2:m
for j = 2:n
tem1 = FF(i,j-1) + M(i,j); % 從左邊來
tem2 = FF(i-1,j) + M(i,j); % 從上面來
FF(i,j) = max(tem1,tem2);
end
end
f = FF(m,n);
% 根據程序中得到的DP數組(FF)來推出對應的路徑path
path = zeros(m,n); % path全為0和1組成，1表示經過該格子
i = m; j = n;
while i ~= 1 || j ~= 1 % 只要沒有回到原點
path(i,j) = 1; % 把path矩陣的第i行第j列變成1（表示訪問了這個格子）
if i == 1 % 如果到了第一行
path(1,1:j) = 1; % 剩余的路徑沿著左邊一直走就可以了
break % 退出循環
end
if j == 1 % 如果到了第一列
path(1:i,1) = 1; % 剩余的路徑沿著上方一直走就可以了
break % 退出循環
end
tmp1 = FF(i-1,j); % 上方單元格FF的值
tmp2 = FF(i,j-1); % 左邊單元格FF的值
ind = find([tmp1,tmp2] == (FF(i,j)-M(i,j)),1); % 看哪個值等於FF(i,j)-M(i,j)
if ind == 1 % 如果上方單元格FF的值等於FF(i,j)-M(i,j)
i = i-1; % 說明上一步沿著上方來的
else % 如果左邊單元格FF的值等於FF(i,j)-M(i,j)
j = j-1; % 說明上一步沿著左邊來的
end
end
end
import numpy as np
matrix= np.array([[5,1,5,1],
[3,5,3,5],
[4,2,1,1],
[1,5,1,3],
[1,5,3,4]],
dtype=int)
a,b=matrix.shape
Matrix=matrix.copy()
Matrix[:,0]=np.cumsum(Matrix[:,0],axis=0,dtype=int)
Matrix[0,:]=np.cumsum(Matrix[0,:],axis=0,dtype=int)
i=0
j=0
for i in range(1,a):
for j in range(1,b):
num1 = Matrix[i][j]+Matrix[i-1][j]#left
num2 = Matrix[i][j]+Matrix[i][j-1]#up
Matrix[i][j]=max(num1,num2)
print("最大值是", Matrix[a-1][b-1])
print("整個矩陣是", Matrix)
i=a
j=b
path= np.zeros((a,b))
while i!=0 and j!=0:
path[i-1][j-1]=1
if i==0:
path[0][0:j]=1
break
if j==0:
path[0:i][0]=1
break
tmp1 = Matrix[i-2][j-1] #up
tmp2 = Matrix[i-1][j-2] #left
if Matrix[i-1][j-1] - matrix[i-1][j-1] == tmp1:
i=i-1
else:
j=j-1
print(path)
>>>>>>>>>>輸出>>>>>>>>>>>>>>>>>>>>>>>
>#總和最大權重的路徑為
>array([[1., 0., 0., 0.],
[1., 1., 0., 0.],
[0., 1., 0., 0.],
[0., 1., 0., 0.],
[0., 1., 1., 1.]])
求最大值的時候是順序的，求路徑得先求出累加和再反向推出路徑，用累加後的矩陣的相鄰兩個值相減，看是否值跟原矩陣相等
