面试题47：礼物的最大价值

从左上到右下只能向右或向下，先用二维动态规划保存到格最优值，再用一维列数组压缩空间。

学习目标

  • 能...
  • 能...
  • 能...
分步1 / 3

核心思路

理解问题的核心算法。

MaxValueOfGifts核心算法示意图
算法核心步骤可视化

从“到达这一格之前在哪里”开始

先预测：站在棋盘内部任意一格时，最后一步只可能来自上方或左方。因为题目规定从左上角出发，只能向右或向下，所以所有到达当前格的合法路径，恰好被这两个来源分成互不重叠的两类。

题目要求收集礼物的最大价值，并不要求先枚举每条路径。更关键的问题是：到达每个格子时，最多已经收集多少价值？把这个量定义清楚，后面的选择就只依赖两个已经解决的子问题。

把从起点到位置行i、列j的最大累计价值称为。若当前礼物价值是value，来自上方的最优值是up，来自左方的是left，那么状态转移为：

best[i][j] = value[i][j] + max(
    best[i - 1][j],
    best[i][j - 1]
)

不存在的方向在作者题设中按0处理。第一格因此是自身价值，第一行只能从左累加，第一列只能从上累加。

图中小字是原礼物价值，大字是到格最优。右下角53不是某一步的局部贪心结果，而是所有合法路径被逐格归并后的全局最优值。

为什么递推不会漏掉更好的路径

对任意格子，它的只有上方和左方。任意完整路径进入当前格时必经其中一个，因此没有第三类路径被遗漏。

再看为什么只保留每个前驱的最大值就够。假设一条经过上方格的路径在到达上方格时不是最优的，把它的前半段替换成上方格的最优路径，后半段仍然合法，且累计价值只会更大。于是经过上方的所有路径只需保留一个最优值；左方同理。最后在两类最优值中取较大者，再加当前礼物价值。

这就是动态规划的最优子结构。未来允许的移动只由当前位置决定，与此前具体走法无关，所以状态具有无后效性。若规则改成“同一行最多连续走两步”或“某把钥匙只能拾取一次”，只用行列坐标就不够，状态还需记录连续步数或钥匙集合。

作者（）第一解：保存完整二维累计表

作者输入不是二维容器，而是一段连续int内存。第i行第j列通过values[i乘cols加j]读取，这种按行连续存放的布局称为。

下面保留作者解法的结构：先检查指针和尺寸，为每一行分配累计数组，逐格填表，取右下角后再逐行释放。

#include <algorithm>
 
int getMaxValue_solution1(
    const int* values,
    int rows,
    int cols) {
    if (values == nullptr ||
        rows <= 0 ||
        cols <= 0) {
        return 0;
    }
 
    int** maxValues = new int*[rows];
    for (int i = 0; i < rows; ++i) {
        maxValues[i] = new int[cols];
    }
 
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            int left = 0;
            int up = 0;
 
            if (i > 0) {
                up = maxValues[i - 1][j];
            }
            if (j > 0) {
                left = maxValues[i][j - 1];
            }
 
            maxValues[i][j] =
                std::max(left, up) +
                values[i * cols + j];
        }
    }
 
    const int result =
        maxValues[rows - 1][cols - 1];
    for (int i = 0; i < rows; ++i) {
        delete[] maxValues[i];
    }
    delete[] maxValues;
    return result;
}

设网格有rows行、cols列。每格计算一次，时间复杂度为O(rows乘cols)；累计表额外占用O(rows乘cols)空间。输入values只读，没有像旧页那样原地覆盖礼物值。

完整表的优势不只是便于讲解。若还要输出路线，可以从右下角反向比较上方与左方的累计值，选择较大的合法前驱，直到回到左上角，再反转所得坐标序列。

对于作者4乘4样例，一条最优路线收集1、12、5、7、7、16、5，合计53。累计值相同时可能存在多条最优路径；“向上优先”或“向左优先”只会选择不同代表，不影响最大价值。

手算4乘4累计表

原礼物矩阵为：

 1  10   3   8
12   2   9   6
 5   7   4  11
 3   7  16   5

第一行只能向右，得到1、11、14、22；第一列只能向下，得到1、13、18、21。其余位置取上、左较大值。例如第二行第三列的礼物是9，上方累计14，左方累计15，所以该格得到24。第四行第三列的礼物是16，上方29，左方32，所以得到48。

完整累计表是：

 1  11  14  22
13  15  24  30
18  25  29  41
21  32  48  53

手算时每填一格都要标注“上、左、当前价值”三个量。只写最终53无法检查状态定义和边界，面试官也无法判断答案是递推所得还是猜出。

作者第二解：只保留一行

计算第i行时，每个新状态只需要上一行同列和当前行前一列。作者用长度为cols的一维数组完成覆盖，这正是一维数组压缩空间。

更新列j之前，maxValues[j]仍保存上一行同列，也就是up；maxValues[j减1]已经在本轮更新，保存当前行左方，也就是left。写回后，maxValues[j]变成当前格到格最优。这一组随扫描位置改变解释、但始终维持上述关系的数组称为。

#include <algorithm>
 
int getMaxValue_solution2(
    const int* values,
    int rows,
    int cols) {
    if (values == nullptr ||
        rows <= 0 ||
        cols <= 0) {
        return 0;
    }
 
    int* maxValues = new int[cols];
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            int left = 0;
            int up = 0;
 
            if (i > 0) {
                up = maxValues[j];
            }
            if (j > 0) {
                left = maxValues[j - 1];
            }
 
            maxValues[j] =
                std::max(left, up) +
                values[i * cols + j];
        }
    }
 
    const int result =
        maxValues[cols - 1];
    delete[] maxValues;
    return result;
}

逐行切换图中的状态，可以看到数组依次变成1、11、14、22，再变成13、15、24、30，最终得到21、32、48、53。时间仍是O(rows乘cols)，额外空间降为O(cols)。

若列数远大于行数，还可转置扫描逻辑，让数组长度取rows与cols的较小者，额外空间降为O(min(rows, cols))。但转置后必须同步修改行主序索引，不能只交换循环变量。

空间压缩为什么会丢失路线

二维累计表保留了每个格子的两个候选值，可从终点逐步判断前驱。一维数组在进入下一行时会覆盖上一行，大部分历史状态消失，因此默认只能返回最大总值，不能直接恢复整条路径。

从终点依据累计表反向寻找最优前驱的过程称为。若既要O(cols)工作空间又要输出路径，可使用分治式路径恢复，或另存每格方向位；后一种仍需要O(rows乘cols)位空间，只是常数比完整整数表小。

不能声称“空间压缩后仍是严格O(cols)，同时免费输出任意长度路径”。输出路径本身至少有rows加cols减1个坐标，输出空间已有线性下界；恢复过程也需要足够信息区分局部并列。

正值契约决定边界能否写0

作者题目明确每件礼物价值大于0。因此在第一行，把不存在的up设为0不会胜过合法的正数left；第一列同理。左上角两个前驱都是0，结果就是起点价值。

如果扩展为允许负数，这一写法会错误地允许路径从网格外“中途进入”。例如一行礼物为负5、负2：合法路径必须从负5开始，总和负7；作者边界在第二格比较left等于负5与up等于0，会选0，错误得到负2。

因此工程扩展不能只改输入注释。状态初值、整数下界与加法溢出都要一起设计。对负无穷哨兵直接加礼物值还可能下溢，最好显式分支处理边界。

更稳健的工程实现

作者使用int累加。若每件礼物接近int上界，路径长度稍大就会有符号溢出。可改用int64_t，并用vector管理内存；以下版本仍按作者正值契约、行主序输入和O(cols)空间工作。

#include <algorithm>
#include <cstdint>
#include <span>
#include <stdexcept>
#include <vector>
 
std::int64_t maxGiftValue(
    std::span<const int> values,
    std::size_t rows,
    std::size_t cols) {
    if (rows == 0 || cols == 0) {
        return 0;
    }
    if (rows > values.size() / cols ||
        rows * cols != values.size()) {
        throw std::invalid_argument(
            "matrix dimensions mismatch");
    }
 
    std::vector<std::int64_t> best(cols, 0);
    for (std::size_t i = 0; i < rows; ++i) {
        for (std::size_t j = 0; j < cols; ++j) {
            if (values[i * cols + j] <= 0) {
                throw std::invalid_argument(
                    "gift values must be positive");
            }
            const std::int64_t up =
                i == 0 ? 0 : best[j];
            const std::int64_t left =
                j == 0 ? 0 : best[j - 1];
            best[j] = std::max(up, left) +
                      values[i * cols + j];
        }
    }
    return best.back();
}

尺寸校验先用除法避免rows乘cols在比较前溢出；随后乘法已知安全。若接口要接受带步长的二维视图，不能再假设行主序连续内存，应把stride纳入索引或传入二维span封装。

作者六组测试逐项核对

作者test辅助函数会分别调用二维解和一维解，并与同一个expected比较：

  1. 3乘3递增矩阵期望29，一条路径是1、4、7、8、9。
  2. 4乘4一般矩阵期望53，覆盖内部格上左竞争。
  3. 单行1、10、3、8期望22，证明第一行只能从左。
  4. 单列1、12、5、3期望21，证明第一列只能从上。
  5. 单格3期望3，证明起点就是终点。
  6. 空指针、0行、0列期望0，证明入口防御分支。

源码定义了test6，但main只调用test1到test5，因此空输入测试实际上没有执行。阅读测试代码时必须核对“函数存在”和“测试已运行”两个层次，不能看到定义就当成覆盖。

#include <cassert>
 
void testMaxGiftValue() {
    const int grid3x3[] = {
        1, 2, 3,
        4, 5, 6,
        7, 8, 9,
    };
    assert(getMaxValue_solution1(
        grid3x3, 3, 3) == 29);
    assert(getMaxValue_solution2(
        grid3x3, 3, 3) == 29);
 
    const int oneRow[] = {1, 10, 3, 8};
    assert(getMaxValue_solution2(
        oneRow, 1, 4) == 22);
 
    const int oneCol[] = {1, 12, 5, 3};
    assert(getMaxValue_solution2(
        oneCol, 4, 1) == 21);
 
    const int oneCell[] = {3};
    assert(getMaxValue_solution2(
        oneCell, 1, 1) == 3);
    assert(getMaxValue_solution2(
        nullptr, 0, 0) == 0);
}

测试还应加入随机小矩阵：枚举所有右下路径求最大值，与二维、一维两版对拍。随机生成器必须遵守正值契约；负值测试应针对重新定义边界后的扩展版本，不能用来否定作者在原题条件下的正确实现。

常见错误与诊断顺序

把状态定义成“从当前格到终点”也能解，但扫描方向应从右下到左上，后继变为右方和下方。若状态定义与循环方向混用，会读取尚未计算的数据。

原地修改输入网格是另一种O(1)额外空间变体，却改变调用者数据，而且不是作者源码给出的两种实现。面试回答可以提出扩展，但要先准确还原作者的二维表和一维列数组，再说明变体的前提与副作用。

贪心地每步选择右方或下方礼物更大者不成立。较大的眼前礼物后面可能接一串小值，较小的下一步可能通向高价值区域。动态规划比较的是“到达前驱的完整累计最优”，不是只比较相邻礼物。

二维数组释放时若只delete外层指针，会泄漏每一行；若对new数组使用标量delete，行为未定义。工程版用vector可消除手工配对风险。

诊断错误答案时按以下顺序检查：状态含义是否固定；第一行第一列是否只来自唯一方向；一维覆盖顺序是否使j减1为当前行、j为上一行；行主序索引是否使用cols；最后返回是否为右下角；测试函数是否真的由main调用。

本章练习

练习

问题 1： 请说明...

问题 2： 请说明...

问题 3： 请说明...

本章回顾

  1. 礼物的最大价值可定义为每格的到格最优，而不是先枚举路径。
  2. 只能向右或向下，所以当前格所有路径恰好来自上方或左方。
  3. 动态规划转移取两个前驱最优的较大者，再加当前礼物价值。
  4. 作者第一解保存rows乘cols累计表，时间和额外空间均为二维规模。
  5. 作者第二解利用一维数组压缩空间，同列更新前是上方，左邻更新后是左方。
  6. 完整累计表可做路径回溯，一维覆盖版默认只保留最大总值。
  7. 缺失前驱设0依赖礼物价值大于0；允许负值时必须重写边界。
  8. 作者定义六组测试，但main遗漏空输入test6，测试覆盖应以实际调用为准。

名词解释

复习本章（5 题）

讨论

评论区加载中…