【题目描述】
在一个 m*n 的棋盘中的每一个格都放一个礼物,每个礼物都有一定的价值(价值大于0).你可以从棋盘的左上角开始拿各种里的礼物,并每次向右或者向下移动一格,直到到达棋盘的右下角。给定一个棋盘及上面个的礼物,请计算你最多能拿走多少价值的礼物?
【思路解析】
动态规划解决,当前格所能获得的最大价值等于max(左边,上边)+该格的价值。采用一个二维数组保存中间结果,最终返回右下角格的价值即可,时间复杂度等于格数。
在此基础上,书中的一种优化方式是,由于当前格的更新只与其上与左的格有关,因此可以只保存当前格左与上的值,用一个长度为cols的一维数组即可,保存下图中的13,11,14,22这四个价值。节约了空间。
在循环体中的更新方式:
up=temp[j]
left=temp[j-1]
temp[j]=max(up,left)+values[i*rows+j]
【代码】
#!coding:utf-8
class Solution:
def getmaxValue(self, values, rows, cols):
if not values or rows<=0 or cols <=0:
return 0
temp = [[0] * cols]*rows
print(temp[1][2])
for i in range(rows):
for j in range(cols):
left = 0
up = 0
if i > 0:
up=temp[i-1][j]
if j > 0:
left=temp[i][j-1]
temp[i][j] = max(up,left) + values[i*rows+j]
return temp[rows-1][cols-1]
s = Solution()
a = s.getmaxValue([1,10,3,8,12,2,9,6,5,7,4,11,3,7,16,5],4,4)
优化:
class Solution:
def getmaxValue(self, values, rows, cols):
if not values or rows<=0 or cols <=0:
return 0
temp = [0] * cols
for i in range(rows):
for j in range(cols):
left = 0
up = 0
if i > 0:
up = temp[j]
if j > 0:
left = temp[j-1]
temp[j] = max(up,left) + values[i*rows+j]
return temp[-1]