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

m*n 棋盘最大礼物价值问题 solution

在一个 m*n 的棋盘中，每个格子都有一个礼物，每个礼物都有一个价值。我们需要从起点 (0,0) 只能向右或向下走，直到走到右下角 (m-1, n-1)，求出沿途所经过的礼物的最大价值。

解决思路

这个问题类似于经典的动态规划问题，可以通过动态规划的方法来解决。目标是找到从起点到终点路径中礼物价值的最大总和。由于只能向右或向下走，所以每个格子的最大价值取决于其左边格子和上边格子的最大值再加上当前格子的礼物价值。

具体来说，我们可以使用一个二维数组 maxGift，其中 maxGift[i][j] 表示到达格子 (i,j) 时的最大礼物价值。在这个数组的基础上，我们可以逐步计算每个格子的最大价值。

这种方法需要一个二维数组来存储中间结果，空间复杂度为 O(mn)，时间复杂度为 O(mn)。

优化空间复杂度

在上述基础上，我们可以通过将 maxGift 换成一个一维数组来优化空间复杂度。具体做法如下：

这种优化后的方法将空间复杂度降低到 O(n) ，时间复杂度仍为 O(mn)。

##代码示例

public int func(int[][] gifts) {    if (gifts == null || gifts.length == 0)        return 0;    // 使用一维数组优化空间复杂度    int n = gifts[0].length;    int[] maxGift = new int[n];    maxGift[0] = gifts[0][0];    for (int i = 1; i < gifts.length; i++) {        for (int j = 0; j < n; j++) {            int up = 0;            if (i > 0)                up = maxGift[j];                        int left = 0;            if (j > 0)                left = maxGift[j - 1];                        maxGift[j] = Math.max(up, left) + gifts[i][j];        }    }    return maxGift[n - 1];}

优化后的空间复杂度 solution

为了进一步优化空间复杂度，我们可以直接将 maxGift 数组重新划分，仅记录必要的信息，而不存储整个二维数组。这通过将上一行的最大值存储在一个一维数组中实现，节省了额外的 O(n) 空间。

以下是优化后的 Java 实现：

public int func2(int[][] gifts) {    if (gifts == null || gifts.length == 0)        return 0;    int n = gifts[0].length;    int[] maxGift = new int[n];    maxGift[0] = gifts[0][0];    for (int i = 1; i < gifts.length; i++) {        for (int j = 0; j < n; j++) {            int up = (i > 0) ? maxGift[j] : Integer.MIN_VALUE;            int left = (j > 0) ? maxGift[j - 1] : Integer.MIN_VALUE;                        maxGift[j] = Math.max(up, left) + gifts[i][j];        }    }    return maxGift[n - 1];}

这个优化后的方法不仅节省了空间，还保持了相同的时间复杂度 O(mn)。

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