【剑指offer】礼物的最大值动态规划

迈不过友情╰ 2022-04-11 10:52 140阅读 0赞

**题目描述**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]  
采用动态规划的方式：f(x, y) = matrix(x, y) + max\[f(x - 1, y), f(x, y - 1)\]并且使用另外一个矩阵保存中间结果，防止重复迭代

class Solution:
        def RecursionOfValue(self, matrix, maxValueMatrix, row, col):
            maxValue = 0
            if row == 0 and col == 0:
                return matrix[0][0]
            if row >= 0 and row < len(matrix) and col >= 0 and col < len(matrix[0]):
                if row >= 1 and maxValueMatrix[row - 1][col] != 0:
                    temp1 = maxValueMatrix[row - 1][col]
                else:
                    temp1 = self.RecursionOfValue(matrix, maxValueMatrix, row - 1, col)
                if col >= 1 and maxValueMatrix[row][col - 1] != 0:
                    temp2 = maxValueMatrix[row][col - 1]
                else:
                    temp2 = self.RecursionOfValue(matrix, maxValueMatrix, row, col - 1)
                maxValue += matrix[row][col] + max(temp1, temp2)
                maxValueMatrix[row][col] = maxValue
            return maxValue
        def MaxValueOfGift(self, matrix):
            if matrix == []:
                return 0
            cols = len(matrix[0])
            rows = len(matrix)
            maxValueMatrix = [([0] * cols) for i in range(rows)]
            return self.RecursionOfValue(matrix, maxValueMatrix, rows - 1, cols - 1)
    matrix = [[1,10,3,8],[12,2,9,6],[5,7,4,11],[3,7,16,5]]
    print(Solution().MaxValueOfGift(matrix))

输出：53

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220411/04c73ab493354a17a717c4c37309dd57.png