【状压DP】3276. 选择矩阵中单元格的最大得分|2403

本文涉及知识点

C++动态规划

3276. 选择矩阵中单元格的最大得分

给你一个由正整数构成的二维矩阵 grid。
你需要从矩阵中选择 一个或多个 单元格，选中的单元格应满足以下条件：
所选单元格中的任意两个单元格都不会处于矩阵的 同一行。
所选单元格的值 互不相同。
你的得分为所选单元格值的总和。
返回你能获得的 最大 得分。
示例 1：
输入： grid = [[1,2,3],[4,3,2],[1,1,1]]
输出： 8
解释：
选择上图中用彩色标记的单元格，对应的值分别为 1、3 和 4 。
示例 2：
输入： grid = [[8,7,6],[8,3,2]]
输出： 15
解释：
选择上图中用彩色标记的单元格，对应的值分别为 7 和 8 。
提示：
1 <= grid.length, grid[i].length <= 10
1 <= grid[i][j] <= 100

状态压缩动态规划

各行升序排序。R是网格的行数，M是$max(grid[r][c])$

动态规划的状态表示

我们选中的降序选择。
dp[m][min] ,(1<<r)&m 表示第r行是否选择。iMin表示选择的最小值。$iMin\in [0,101]$。
空间复杂度：$O(2^{N}M)$

动态规划的填表顺序

m从0到大，iMin任意升序。枚举前驱状态。

动态规划的转移方程

每种状态： 枚举从第r行选择：
it = lower(grid[r],iMin)
如果it 是首元素：
MaxSelf(dp[m ^(1<<r)][min],dp[m][min])
不是首元素：
–it。
MaxSelf(dp[m ^(1<<r)][min] ,dp[m][min]+*it)
时间复杂度：$O(N{2}^{N}MlogC)$

动态规划的初始值

全为0

动态规划的返回值

dp.back().back()