牛妹的礼物

[编程题]牛妹的礼物

热度指数：10588 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

众所周知，牛妹有很多很多粉丝，粉丝送了很多很多礼物给牛妹，牛妹的礼物摆满了地板。

地板是 $N\times M$ 的格子，每个格子有且只有一个礼物，牛妹已知每个礼物的体积。

地板的坐标是左上角(1,1) 右下角（N, M）。

牛妹只想要从屋子左上角走到右下角，每次走一步，每步只能向下走一步或者向右走一步或者向右下走一步

每次走过一个格子，拿起（并且必须拿上）这个格子上的礼物。

牛妹想知道，她能走到最后拿起的所有礼物体积最小和是多少？

示例1

输入

[[1,2,3],[2,3,4]]

输出

说明

先走到(1,1)这个点，此时和为1，然后走到(1,2)这个点，拿起(1,2)点的数字，此时和为3，最后走到(2,3)，拿起(2,3)点的数字，此时和为7

备注:

0<N,M<300
0<=每个礼物的体积<100

算法知识视频讲解

Python

角三落

注意审题，可以右/下/右下这么三种走法

gift[m][n] = min(gift[m-1][n],gift[m][n-1],gift[m-1][n-1]) + presentVolumn[m][n]

编辑于 2020-11-10 15:05:38 回复(0)

Python

无名老张

class Solution:
    def selectPresent(self , presentVolumn ):
        # write code here
                # 首先考虑数组为空的情况
        if not presentVolumn: return 0
                # 计算出数组的维度
        N, M = len(presentVolumn),len(presentVolumn[0])
                # 初始化dp数组
        dp = [[float("inf") for i in range(M+1)] for j in range(N+1)]
        dp[0][0] = 0
        
        for i in range(1,N+1):
            dp[i][0] = dp[i-1][0] + presentVolumn[i-1][0]
        for j in range(1,M+1):
            dp[0][j] = dp[0][j-1] + presentVolumn[0][j-1]

        for i in range(1,N+1):
            for j in range(1,M+1):
                                # 状态转移方程
                dp[i][j] = presentVolumn[i-1][j-1] + min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])
        return dp[N][M]

发表于 2020-08-07 19:59:47 回复(0)

Python