LeetCode 补充题 173. 矩阵两端取数的最大得分

2026-09-13 HGNULB 约 4 分钟

文章信息 2 个分类 2 个标签

分类

补充题中等

题目描述

牛客原题： ✅ 补充题 173. 矩阵两端取数的最大得分

给定一个非空非负整数矩阵 matrix，每轮从每一行的左端或右端各取一个数。第 i 轮所取数的得分是该数乘 2^i，i 从 1 开始。

全部取完后求最大总分，再对 1000000007 取模。

示例 1：

输入： matrix = [[1,2,3],[3,4,2]]
输出： 82
解释： 第一行依次取 1、2、3，得分 2+8+24；第二行依次取 2、3、4，得分 4+12+32，总分为 82。

提示：

矩阵非空，行数和列数均不超过 100，元素在 0…1000 范围内。
每轮每行恰好取一个数，轮次从 1 开始。
先求最大真实总分，再对 1000000007 取模。

题意分析

每轮每行都独立选左端或右端，一行的选择不会限制另一行。因此总最优值等于各行最优值之和，先解决一行的取数顺序，再累加即可。

权重随轮次增长，不能只比较眼前两端大小。取走若干元素后剩余部分始终是一个连续区间，可以用其左右边界描述状态。

解法：逐行区间 DP 比较真实大整数得分

核心思路

[!blue]

一行共有 m 个数，若剩余区间长度为 len，说明已取 m-len 次，下一轮权重为 2^(m-len+1)。dp[l][r] 保存从此剩余区间取完的最大得分，轮次由区间长度唯一确定，无需另加状态维度。

下一步只能取左端或右端，分别得到当前端点乘本轮权重，加上缩短区间的最优值；两者取最大。单元素区间对应最后一轮，初始化为该值乘 2^m，之后按长度递增计算。

2^100 已超过 64 位，所有比较使用大整数真实值。Go 的乘加接收者使用新对象，不改动共享幂和子问题值；累加各行最优值后最后取模，不能用模值决定哪条路径更优。

解题步骤

预计算 2 的各次幂，每行单独建立区间 DP。

长度为 1 的区间对应最后一轮，赋予 2^m 权重。

按区间长度递增，比较取左端或右端后的总分，轮次为 m-length+1。

累加每行最大值，最终答案才取模。

代码实现

class Solution {
    public int matrixScore(int[][] matrix) {
        int m = matrix[0].length;
        BigInteger[] power = new BigInteger[m + 1];

        for (int i = 0; i <= m; i++) {
            power[i] = BigInteger.ONE.shiftLeft(i);
        }

        BigInteger total = BigInteger.ZERO;

        for (int[] row : matrix) {
            BigInteger[][] dp = new BigInteger[m][m];

            for (int i = 0; i < m; i++) {
                dp[i][i] = power[m].multiply(BigInteger.valueOf(row[i]));
            }

            for (int len = 2; len <= m; len++) {
                for (int l = 0; l + len <= m; l++) {
                    int r = l + len - 1;
                    int turn = m - len + 1;
                    BigInteger left =
                            power[turn].multiply(BigInteger.valueOf(row[l])).add(dp[l + 1][r]);
                    BigInteger right =
                            power[turn].multiply(BigInteger.valueOf(row[r])).add(dp[l][r - 1]);

                    dp[l][r] = left.max(right);
                }
            }

            total = total.add(dp[0][m - 1]);
        }

        return total.mod(BigInteger.valueOf(1_000_000_007)).intValue();
    }
}

import "math/big"

func matrixScore(matrix [][]int) int {
    m := len(matrix[0])
    power := make([]*big.Int, m+1)
    for i := range power {
        power[i] = new(big.Int).Lsh(big.NewInt(1), uint(i))
    }
    total := new(big.Int)
    for _, row := range matrix {
        dp := make([][]*big.Int, m)
        for i := range dp {
            dp[i] = make([]*big.Int, m)
            dp[i][i] = new(big.Int).Mul(power[m], big.NewInt(int64(row[i])))
        }
        for length := 2; length <= m; length++ {
            for l := 0; l+length <= m; l++ {
                r, turn := l+length-1, m-length+1
                left := new(big.Int).Mul(power[turn], big.NewInt(int64(row[l])))
                left.Add(left, dp[l+1][r])
                right := new(big.Int).Mul(power[turn], big.NewInt(int64(row[r])))
                right.Add(right, dp[l][r-1])
                if left.Cmp(right) < 0 {
                    left = right
                }
                dp[l][r] = left
            }
        }
        total.Add(total, dp[0][m-1])
    }
    return int(total.Mod(total, big.NewInt(1_000_000_007)).Int64())
}

复杂度分析

时间复杂度：n行m列，执行 $O(nm^2)$ 次大整数运算。

空间复杂度：DP占 $O(m^2)$ 个大整数，每个数的位数为 $O(m+\log V)$。

关键点总结

[!green]

每行的操作互不制约，所以总最优值等于逐行最优值之和；最大值比较必须保留真实大整数，取模后的大小没有意义。

易错点总结

[!yellow]

轮次从1开始；必须先比较原始大整数，再取模；Go的big.Int会修改接收者，不能覆盖共享的幂或子问题值。

相似题目

题目	难度	关联与区别
1770. 执行乘法运算的最大分数	困难	同样从数组两端取数并乘当前轮次权重，本题逐行独立计算且幂次权重需要大整数。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/20725430

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！