DeepSeek LeetCode 3276. 选择矩阵中单元格的最大得分 C语言实现

这道题在 C 语言中非常适合用状态压缩动态规划 (状压DP) 来解决因为行数 n 最多只有 10。与 Java 的二维 DP 不同这里我采用一维 DP 按数值倒序遍历的优化写法效率更高且代码更简洁。 核心思路1. 预处理因为数值范围只有 1 到 100我们统计每个数值出现在了哪些行用一个位掩码表示。2. 状态定义dp[mask] 表示“已占用行”状态为 mask 时能获得的最大得分。3. 数值倒序从 100 到 1 遍历每个数值 v。· 对于当前状态 mask如果数值 v 出现在某些行rows且这些行中有未被占用的available rows ~mask我们可以选择其中一个行 r。· 转移方程dp[mask | (1r)] max(dp[mask | (1r)], dp[mask] v)。4. 关键技巧倒序遍历 mask从大到小可以确保同一个数值 v 在本轮中不会被重复使用因为 newMask mask先处理大的 mask 可以避免同层更新传递。 C 语言代码实现c#include string.h#include limits.hint maxScore(int** grid, int gridSize, int* gridColSize) {// 1. 预处理valueMask[v] 记录数值 v 出现在哪些行二进制位表示int valueMask[101] {0};for (int i 0; i gridSize; i) {for (int j 0; j gridColSize[i]; j) {int v grid[i][j];valueMask[v] | (1 i); // 标记第 i 行包含数值 v}}int totalMasks 1 gridSize;int dp[1024]; // gridSize 10所以 1024 足够// 初始化为 -1 表示不可达for (int i 0; i totalMasks; i) dp[i] -1;dp[0] 0; // 初始状态没有行被占用// 2. 从大到小遍历所有可能的数值for (int v 100; v 1; v--) {int rows valueMask[v];if (rows 0) continue; // 该数值不存在跳过// 倒序遍历 mask保证每个数值 v 在本轮只被使用一次// 因为 newMask mask | bit mask从大到小能防止同层污染for (int mask totalMasks - 1; mask 0; mask--) {if (dp[mask] 0) continue; // 当前状态不可达// 找出包含数值 v 且尚未被占用的行int available rows ~mask;while (available) {// 取出最低位的 1int bit available -available;int newMask mask | bit;int candidate dp[mask] v;if (candidate dp[newMask]) {dp[newMask] candidate;}// 移除最低位的 1available - bit;}}}// 3. 在所有合法状态中取最大值int ans 0;for (int mask 0; mask totalMasks; mask) {if (dp[mask] ans) ans dp[mask];}return ans;} 代码细节解读· valueMask[v] | (1 i)由于每一行最多选一个数字我们只关心某个数字出现在了哪些行重复出现并不影响决策。· 倒序循环 mask这是避免同一数值被重复选用的关键。因为 newMask mask从大到小处理 mask 时dp[mask] 不会在本轮被更小的 mask 更新从而确保了每个数值 v 只会被添加一次。· available -available这是位运算中取最低位 1 的经典写法用于高效枚举可用的行。⏱️ 复杂度分析· 时间复杂度O(100 * 2^n * n)其中 n 是矩阵行数n 10效率极高。· 空间复杂度O(2^n)仅使用了一维 DP 数组。这个实现充分利用了 C 语言的位运算优势简洁且高效。如果行数 gridSize 较小dp 数组甚至可以放在栈上但为了稳妥这里使用了固定大小数组。