LCR166.珠宝的最高价值

链接：LCR166.珠宝的最高价值
难度：Medium
标签：数组、动态规划、矩阵
简介：给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？。

题解 1 - cpp

• 编辑时间：2023-03-08
• 执行用时：8ms
• 内存消耗：9MB
• 编程语言：cpp
• 解法介绍：dp[i][j]表示i行j列时最多能拿多少礼物。

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size(), dp[205][205] = {0};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j] = grid[i][j];
                if (i == 0 && j != 0) dp[i][j] += dp[i][j - 1];
                else if (i != 0 && j == 0) dp[i][j] += dp[i - 1][j];
                else if (i != 0 && j != 0)dp[i][j] += max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n - 1][m - 1];
    }
};

题解 2 - python

• 编辑时间：2023-03-08
• 执行用时：64ms
• 内存消耗：17.6MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        dp = [[grid[i][j] for j in range(m)] for i in range(n)]
        for i in range(n):
            for j in range(m):
                if i == 0 and j != 0:
                    dp[i][j] += dp[i][j - 1]
                elif i != 0 and j == 0:
                    dp[i][j] += dp[i - 1][j]
                elif i != 0 and j != 0:
                    dp[i][j] += max(dp[i - 1][j], dp[i][j - 1])
        return dp[n-1][m-1]

题解 3 - rust

• 编辑时间：2023-03-08
• 执行用时：4ms
• 内存消耗：2.5MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
        pub fn max_value(grid: Vec<Vec<i32>>) -> i32 {
            let (n, m) = (grid.len(), grid[0].len());
            let mut dp = vec![vec![0; m]; n];
            for i in 0..n {
                for j in 0..m {
                    dp[i][j] = grid[i][j];
                    if i == 0 && j != 0 {
                        dp[i][j] += dp[i][j - 1];
                    } else if i != 0 && j == 0 {
                        dp[i][j] += dp[i - 1][j];
                    } else if i != 0 && j != 0 {
                        dp[i][j] += dp[i - 1][j].max(dp[i][j - 1]);
                    }
                }
            }
            dp[n - 1][m - 1]
        }
    }