47 礼物最大价值

1.特殊情况，空数组，单行单列单独考虑
2.先计算第一行和第一列的dp值，只用累加前面的就可以。
3.动态规划计算

class Solution():
    def maxvalue(self,A):
        m = len(A)
        if m == 0:
            return 0
        n = len(A[0])
        if n == 0:
            return 0

        dp = [[0]*n for i in range(m)]
        dp[0][0] = A[0][0]
        for i in range(1,m):
            dp[i][0] = dp[i-1][0] +A[i][0]
        for j in range(1,n):
            dp[0][j] = dp[0][j-1]+A[0][j]


        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])+A[i][j]

        return dp[m-1][n-1]

s = Solution()
A = [[1,10,3,8],
[12,2,9,6],
[5,7,4,11],
[3,7,16,5]]

print(s.maxvalue(A))