题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

import copy
class Solution(object):
    def getMaxValue(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # f = copy.deepcopy(grid)
        # h = len(grid)
        # w = len(grid[0])
        # # f = [[] for i in range(h)]
        # # print(h, w, f)

        # for i in range(h):
        #     for j in range(w):
        #         if i==0 and j==0:     # 判断边界问题，
        #             f[i][j] = grid[i][j]
        #         else:
        #             if i-1 <0 and j-1>=0:
        #                 f[i][j] = f[i][j-1] + grid[i][j]   
        #             elif i-1 >=0 and j-1<0:
        #                 f[i][j] = f[i-1][j] + grid[i][j]
        #             else:
        #                 f[i][j] = max(f[i-1][j], f[i][j-1]) + grid[i][j]


        # return f[h-1][w-1]

        # 方法二：用0补偿边界   0,0,0,0
        #   [2,3,1],            0,2,3,1   
        #   [1,7,1],  -->       0,1,7,1
        #   [4,6,1],            0,4,6,1
        #
        h = len(grid)
        w = len(grid[0])
        f = []
        for i in range(h+1):
            f.append([0] * (w+1))

        for i in range(1, h+1):
            for j in range(1, w+1):
                f[i][j] = max(f[i-1][j], f[i][j-1]) + grid[i-1][j-1]  # 用0来代替边界

        return f[h][w]

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla