本文共 1339 字，大约阅读时间需要 4 分钟。

在一个 m*n 的棋盘上，每一格都有一个礼物，礼物的价值大于0。我们可以从左上角开始，每次向右或向下移动一格，直到到达右下角。目标是计算最多能拿到的礼物价值。

代码解释

class Solution {    public:        int maxValue(vector
   
    
     > grid) {            int row = grid.size();            int col = grid[0].size();            if (row <= 0 || col <= 0) {                return 0;            }                        // 预处理：左边累加和            for (int i = 1; i < row; ++i) {                grid[i][0] += grid[i-1][0];            }                        // 预处理：上面累加和            for (int i = 1; i < col; ++i) {                grid[0][i] += grid[0][i-1];            }                        // 计算路径最大值            for (int i = 1; i < row; ++i) {                for (int j = 1; j < col; ++j) {                    grid[i][j] += max(grid[i-1][j], grid[i][j-1]);                }            }                        return grid[row-1][col-1];        }}
    
   

代码逻辑

样例测试

假设一个2x2的棋盘，礼物价值如下：

1 23 4

• 预处理阶段：
  • 第2行第1列：3 + 1 = 4
  • 第1行第2列：2 + 1 = 3
• 动态规划求解：
  • 右下角价值：4 + max(3, 4) = 8
• 返回结果为8。

优化点

• 预处理阶段：通过两个循环分别处理行和列的累加，确保每一个中间节点的计算基于正确的前置数据。
• 动态规划阶段：通过取最大值确保路径的正确性，只走收益最大的路径。

该算法的时间复杂度为O(n*m)，适用于所有尺寸的棋盘。动态规划的方法确保了在路径依赖的问题中正确求解最大价值。

转载地址：http://niacz.baihongyu.com/